Submission #199567

#	Time	Username	Problem	Language	Result	Execution time	Memory
199567		SamAnd	Klasika (COCI20_klasika)	C++17	110 / 110	4152 ms	460684 KiB

klasika

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 200005;

int n, m;
pair<int, int> b[N];
vector<int> a[N];
int d[N];

int ti, tin[N], tout[N];
void dfs(int x)
{
    tin[x] = ++ti;
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        dfs(h);
    }
    tout[x] = ti;
}

int z;
int t[N * 20][2];
set<int> s[N * 20];

void ubd(int x, int y)
{
    int pos = 0;
    for (int i = 30; i >= 0; --i)
    {
        int u;
        if (!(y & (1 << i)))
            u = 0;
        else
            u = 1;
        if (!t[pos][u])
        {
            t[pos][u] = ++z;
        }
        pos = t[pos][u];
        s[pos].insert(x);
    }
}

int qry(int l, int r, int y)
{
    int pos = 0;
    int ans = 0;
    for (int i = 30; i >= 0; --i)
    {
        int u;
        if (!(y & (1 << i)))
            u = 0;
        else
            u = 1;
        if (t[pos][(u ^ 1)])
        {
            set<int>::iterator it = s[t[pos][(u ^ 1)]].lower_bound(l);
            if (it != s[t[pos][(u ^ 1)]].end() && (*it) <= r)
            {
                ans += (1 << i);
                pos = t[pos][(u ^ 1)];
            }
            else
                pos = t[pos][u];
        }
        else
        {
            pos = t[pos][u];
        }
    }
    return ans;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d", &m);
    n = 1;
    for (int i = 1; i <= m; ++i)
    {
        char ty[10];
        scanf(" %s", ty);
        if (ty[0] == 'A')
        {
            int x, y;
            scanf("%d%d", &x, &y);
            ++n;
            a[x].push_back(n);
            d[n] = (d[x] ^ y);
            b[i] = m_p(n, -1);
        }
        else
        {
            int x, y;
            scanf("%d%d", &x, &y);
            b[i] = m_p(x, y);
        }
    }
    dfs(1);
    ubd(tin[1], d[1]);
    for (int i = 1; i <= m; ++i)
    {
        if (b[i].second == -1)
        {
            int x = b[i].first;
            ubd(tin[x], d[x]);
        }
        else
        {
            int x = b[i].first;
            int y = b[i].second;
            printf("%d\n", qry(tin[y], tout[y], d[x]));
        }
    }
    return 0;
}

Compilation message (stderr)

klasika.cpp: In function 'void dfs(int)':
klasika.cpp:15:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
klasika.cpp: In function 'int main()':
klasika.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &m);
     ~~~~~^~~~~~~~~~
klasika.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", ty);
         ~~~~~^~~~~~~~~~~
klasika.cpp:88:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~
klasika.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44