oj.uz

Submission #199567

# Submission time Handle Problem Language Result Execution time Memory
199567 2020-02-02T04:22:14 Z SamAnd Klasika (COCI20_klasika) C++17
110 / 110
 4152 ms 460684 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;
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

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

# Verdict Execution time Memory Grader output
1 Correct 116 ms 193016 KB Output is correct
2 Correct 114 ms 193016 KB Output is correct
3 Correct 113 ms 193272 KB Output is correct
4 Correct 118 ms 193192 KB Output is correct
5 Correct 114 ms 192888 KB Output is correct
6 Correct 114 ms 193016 KB Output is correct
7 Correct 121 ms 193144 KB Output is correct
8 Correct 117 ms 193144 KB Output is correct
9 Correct 114 ms 193016 KB Output is correct
10 Correct 113 ms 193016 KB Output is correct
11 Correct 119 ms 193144 KB Output is correct
12 Correct 117 ms 193148 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 193016 KB Output is correct
2 Correct 114 ms 193016 KB Output is correct
3 Correct 113 ms 193272 KB Output is correct
4 Correct 118 ms 193192 KB Output is correct
5 Correct 114 ms 192888 KB Output is correct
6 Correct 114 ms 193016 KB Output is correct
7 Correct 121 ms 193144 KB Output is correct
8 Correct 117 ms 193144 KB Output is correct
9 Correct 114 ms 193016 KB Output is correct
10 Correct 113 ms 193016 KB Output is correct
11 Correct 119 ms 193144 KB Output is correct
12 Correct 117 ms 193148 KB Output is correct
13 Correct 116 ms 193656 KB Output is correct
14 Correct 120 ms 194296 KB Output is correct
15 Correct 127 ms 195144 KB Output is correct
16 Correct 121 ms 195576 KB Output is correct
17 Correct 119 ms 193656 KB Output is correct
18 Correct 121 ms 194296 KB Output is correct
19 Correct 123 ms 194936 KB Output is correct
20 Correct 125 ms 195576 KB Output is correct
21 Correct 121 ms 193584 KB Output is correct
22 Correct 121 ms 194296 KB Output is correct
23 Correct 124 ms 195064 KB Output is correct
24 Correct 124 ms 195576 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1183 ms 262260 KB Output is correct
2 Correct 1809 ms 327564 KB Output is correct
3 Correct 2669 ms 392008 KB Output is correct
4 Correct 3548 ms 460560 KB Output is correct
5 Correct 1220 ms 263152 KB Output is correct
6 Correct 2043 ms 327288 KB Output is correct
7 Correct 2855 ms 389820 KB Output is correct
8 Correct 3907 ms 453540 KB Output is correct
9 Correct 1065 ms 263360 KB Output is correct
10 Correct 1875 ms 328476 KB Output is correct
11 Correct 2679 ms 392028 KB Output is correct
12 Correct 3322 ms 455112 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 193016 KB Output is correct
2 Correct 114 ms 193016 KB Output is correct
3 Correct 113 ms 193272 KB Output is correct
4 Correct 118 ms 193192 KB Output is correct
5 Correct 114 ms 192888 KB Output is correct
6 Correct 114 ms 193016 KB Output is correct
7 Correct 121 ms 193144 KB Output is correct
8 Correct 117 ms 193144 KB Output is correct
9 Correct 114 ms 193016 KB Output is correct
10 Correct 113 ms 193016 KB Output is correct
11 Correct 119 ms 193144 KB Output is correct
12 Correct 117 ms 193148 KB Output is correct
13 Correct 116 ms 193656 KB Output is correct
14 Correct 120 ms 194296 KB Output is correct
15 Correct 127 ms 195144 KB Output is correct
16 Correct 121 ms 195576 KB Output is correct
17 Correct 119 ms 193656 KB Output is correct
18 Correct 121 ms 194296 KB Output is correct
19 Correct 123 ms 194936 KB Output is correct
20 Correct 125 ms 195576 KB Output is correct
21 Correct 121 ms 193584 KB Output is correct
22 Correct 121 ms 194296 KB Output is correct
23 Correct 124 ms 195064 KB Output is correct
24 Correct 124 ms 195576 KB Output is correct
25 Correct 1183 ms 262260 KB Output is correct
26 Correct 1809 ms 327564 KB Output is correct
27 Correct 2669 ms 392008 KB Output is correct
28 Correct 3548 ms 460560 KB Output is correct
29 Correct 1220 ms 263152 KB Output is correct
30 Correct 2043 ms 327288 KB Output is correct
31 Correct 2855 ms 389820 KB Output is correct
32 Correct 3907 ms 453540 KB Output is correct
33 Correct 1065 ms 263360 KB Output is correct
34 Correct 1875 ms 328476 KB Output is correct
35 Correct 2679 ms 392028 KB Output is correct
36 Correct 3322 ms 455112 KB Output is correct
37 Correct 1857 ms 265720 KB Output is correct
38 Correct 2710 ms 330852 KB Output is correct
39 Correct 3221 ms 396792 KB Output is correct
40 Correct 3836 ms 460684 KB Output is correct
41 Correct 2214 ms 263708 KB Output is correct
42 Correct 2999 ms 327440 KB Output is correct
43 Correct 3724 ms 390184 KB Output is correct
44 Correct 4152 ms 452952 KB Output is correct
45 Correct 2172 ms 263644 KB Output is correct
46 Correct 3002 ms 328364 KB Output is correct
47 Correct 3572 ms 391456 KB Output is correct
48 Correct 4144 ms 455356 KB Output is correct