The problem is already stated in the topic name. I have KMP values and I need to recover Z function values and vice versa. Thank you!

Пусть мы объявили переменные a and b в программе. Следующие 2 куска кода выполняются идентично.

1.

a = 1;
b = 1;

2.

a = b = 1;

Но есть ли такой стиль кода (Google C++ Style Guide не дал мне ответа), который утверждает, что какой-то из них предпочтительней?

It is a well-known task to answer whether a node is an ancestor to another one with time complexity O(n) for preprocessing and O(1) for a query.

Each time you enter the node in recursive function DFS, you increase the time counter by one and call it an "entrance" time, and after recursively processing its sons, you increase the time counter by one and call it an "exit" time. Here is the pseudocode.

DFS(u, p): // u is the current node, p is its parent
    increase the timer counter
    in[u] = timer
    for all (u, v) in edges:
        if v != p:
            DFS(v, u)
    increase the timer counter
    out[u] = timer

Now u is an ancestor of v .

Is there someway to implement the same algorithm but with non-recursive DFS?

Дана прямая l, заданная уравнением ax + by + c = 0 и точка P(x₀, y₀). Пусть Q(x₁, y₁) — проекция P на l. Я прав, что ?

I really liked the previous year's post on IOI participants so I decided to do the same for this year.

UPD: Colors updated

If you know any other countries' delegations, let me know in the comments. Thanks!

У кого-нибудь были проблемы с сдачей задач из-за того, что забыли инициализировать глобальную переменную?

И стоит ли мне всегда инициализировать переменные при их создании?

P.S. Я говорю о C++. Инициализируются ли все глобальные переменыые по умолчанию "нулями"? Или это зависит от компилятора?

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#define MX 1000005
using namespace std;

struct BN
{
    int siz, num[MX];
    BN()
    {
        siz = 1;
        memset(num, 0, sizeof(num));
    }
    BN(string &a)
    {
        siz = a.size();
        memset(num, 0, sizeof(num));
        for (int i = 0; i < a.size(); i++)
            num[i] = a[a.size() - i - 1] - '0';
    }
    void len()
    {
        siz = MX - 1;
        while (siz > 0 && num[siz] == 0)
            siz--;
        siz++;
    }
    void inc()
    {
        num[0]++;
        for (int i = 0; i < MX - 1; i++)
        {
            num[i + 1] += num[i] / 10;
            num[i] %= 10;
        }
        len();
    }
    string tostring()
    {
        string a;
        for (int i = siz - 1; i >= 0; i--)
            a += (char)(num[i] + '0');
        return a;
    }
};

BN w;
string s, t, u, v, v1;

string sol()
{
    if (s.size() % 2 == 1)
    {
        u = s.substr(0, s.size() / 2 + 1);
        v = u;
        reverse(v.begin(), v.end());
        v = u + v.substr(1);
        if (v <= s)
        {
            w = BN(u);
            w.inc();
            u = w.tostring();
            v = u;
            reverse(v.begin(), v.end());
            v = u + v.substr(1);
        }
        u = s.substr(0, s.size() / 2);
        v1 = u;
        reverse(v1.begin(), v1.end());
        v1 = u + s[s.size() / 2] + v1;
        if (v1 <= s)
        {
            w = BN(u);
            w.inc();
            u = w.tostring();
            v1 = u;
            reverse(v1.begin(), v1.end());
            v1 = u + s[s.size() / 2] + v1;
        }
        if (v < v1)
            return v;
        return v1;
    }
    u = s.substr(0, s.size() / 2);
    v = u;
    reverse(v.begin(), v.end());
    v = u + v;
    if (v <= s)
    {
        w = BN(u);
        w.inc();
        u = w.tostring();
        v = u;
        reverse(v.begin(), v.end());
        v = u + v;
    }
    return v;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> s;
        t = sol();
        cout << t << "\n";
    }
}

У меня есть решение этой задачи (еще неизвестно верное или нет), но пост создан не для этого. Каждый раз, запуская sol(), у программы crash и SIGSEGV.

Кто-нибудь может объяснить почему?

P.S. BN — структура длинного числа, просто использовал для увеличения числа на один.

Дан взвешенный ориентированный граф с ребрами с весами либо 0 либо 1. Найти кратчайший путь. Я слышал что эту задачу решают BFSом и деком, но не знаю как предотвратить добавление одной вершины в дек несколько раз. Какой условие надо поставить на добавление в дек? Спасибо.