oj.uz

Submission #199564

# Submission time Handle Problem Language Result Execution time Memory
199564 2020-02-02T03:50:09 Z SamAnd Klasika (COCI20_klasika) C++17
33 / 110
 1262 ms 524292 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24440 KB Output is correct
2 Correct 22 ms 24696 KB Output is correct
3 Correct 23 ms 25312 KB Output is correct
4 Correct 23 ms 25976 KB Output is correct
5 Correct 27 ms 24440 KB Output is correct
6 Correct 21 ms 24824 KB Output is correct
7 Correct 23 ms 25336 KB Output is correct
8 Correct 25 ms 26104 KB Output is correct
9 Correct 20 ms 24440 KB Output is correct
10 Correct 22 ms 25084 KB Output is correct
11 Correct 23 ms 25464 KB Output is correct
12 Correct 24 ms 26104 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24440 KB Output is correct
2 Correct 22 ms 24696 KB Output is correct
3 Correct 23 ms 25312 KB Output is correct
4 Correct 23 ms 25976 KB Output is correct
5 Correct 27 ms 24440 KB Output is correct
6 Correct 21 ms 24824 KB Output is correct
7 Correct 23 ms 25336 KB Output is correct
8 Correct 25 ms 26104 KB Output is correct
9 Correct 20 ms 24440 KB Output is correct
10 Correct 22 ms 25084 KB Output is correct
11 Correct 23 ms 25464 KB Output is correct
12 Correct 24 ms 26104 KB Output is correct
13 Correct 36 ms 30516 KB Output is correct
14 Correct 51 ms 37868 KB Output is correct
15 Correct 69 ms 45804 KB Output is correct
16 Correct 89 ms 53924 KB Output is correct
17 Correct 35 ms 30132 KB Output is correct
18 Correct 50 ms 37544 KB Output is correct
19 Correct 72 ms 45096 KB Output is correct
20 Correct 93 ms 52764 KB Output is correct
21 Correct 36 ms 30260 KB Output is correct
22 Correct 53 ms 37672 KB Output is correct
23 Correct 65 ms 45292 KB Output is correct
24 Correct 85 ms 52888 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 1262 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 24440 KB Output is correct
2 Correct 22 ms 24696 KB Output is correct
3 Correct 23 ms 25312 KB Output is correct
4 Correct 23 ms 25976 KB Output is correct
5 Correct 27 ms 24440 KB Output is correct
6 Correct 21 ms 24824 KB Output is correct
7 Correct 23 ms 25336 KB Output is correct
8 Correct 25 ms 26104 KB Output is correct
9 Correct 20 ms 24440 KB Output is correct
10 Correct 22 ms 25084 KB Output is correct
11 Correct 23 ms 25464 KB Output is correct
12 Correct 24 ms 26104 KB Output is correct
13 Correct 36 ms 30516 KB Output is correct
14 Correct 51 ms 37868 KB Output is correct
15 Correct 69 ms 45804 KB Output is correct
16 Correct 89 ms 53924 KB Output is correct
17 Correct 35 ms 30132 KB Output is correct
18 Correct 50 ms 37544 KB Output is correct
19 Correct 72 ms 45096 KB Output is correct
20 Correct 93 ms 52764 KB Output is correct
21 Correct 36 ms 30260 KB Output is correct
22 Correct 53 ms 37672 KB Output is correct
23 Correct 65 ms 45292 KB Output is correct
24 Correct 85 ms 52888 KB Output is correct
25 Runtime error 1262 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -