Submission #199564

#	Time	Username	Problem	Language	Result	Execution time	Memory
199564		SamAnd	Klasika (COCI20_klasika)	C++17	33 / 110	1262 ms	524292 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[N * 4];
vector<vector<int> > t[N * 4];

void bil(int tl, int tr, int pos)
{
    t[pos].push_back({0, 0});
    if (tl == tr)
        return;
    int m = (tl + tr) / 2;
    bil(tl, m, pos * 2);
    bil(m + 1, tr, pos * 2 + 1);
}

void ubd(int tl, int tr, int x, int y, int pos)
{
    int bpos = 0;
    for (int i = 30; i >= 0; --i)
    {
        int u;
        if (!(y & (1 << i)))
            u = 0;
        else
            u = 1;
        if (!t[pos][bpos][u])
        {
            t[pos][bpos][u] = ++z[pos];
            t[pos].push_back({0, 0});
        }
        bpos = t[pos][bpos][u];
    }
    if (tl == tr)
        return;
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(tl, m, x, y, pos * 2);
    else
        ubd(m + 1, tr, x, y, pos * 2 + 1);
}

int qry(int tl, int tr, int l, int r, int y, int pos)
{
    if (l > r)
        return 0;
    if (tl == l && tr == r)
    {
        int bpos = 0;
        int ans = 0;
        if (z[pos] == 0)
            return ans;
        for (int i = 30; i >= 0; --i)
        {
            int u;
            if (!(y & (1 << i)))
                u = 0;
            else
                u = 1;
            if (t[pos][bpos][(u ^ 1)])
            {
                ans += (1 << i);
                bpos = t[pos][bpos][(u ^ 1)];
            }
            else
            {
                bpos = t[pos][bpos][u];
            }
        }
        return ans;
    }
    int m = (tl + tr) / 2;
    return max(qry(tl, m, l, min(m, r), y, pos * 2),
               qry(m + 1, tr, max(m + 1, l), r, y, pos * 2 + 1));
}

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);
    bil(1, n, 1);
    ubd(1, n, tin[1], d[1], 1);
    for (int i = 1; i <= m; ++i)
    {
        if (b[i].second == -1)
        {
            int x = b[i].first;
            ubd(1, n, tin[x], d[x], 1);
        }
        else
        {
            int x = b[i].first;
            int y = b[i].second;
            printf("%d\n", qry(1, n, tin[y], tout[y], d[x], 1));
        }
    }
    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:99:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &m);
     ~~~~~^~~~~~~~~~
klasika.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", ty);
         ~~~~~^~~~~~~~~~~
klasika.cpp:108: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:117: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: 0 / 33
• Subtask 4: 0 / 44