oj.uz

Submission #487900

# Submission time Handle Problem Language Result Execution time Memory
487900 2021-11-17T01:47:19 Z hoanghq2004 Klasika (COCI20_klasika) C++14
33 / 110
 1148 ms 524292 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

const int Nmax = 2e5 + 10;

struct Trie {
    vector <array <int, 2> > to;
    int sz = 0;
    Trie() {
        to.push_back(array <int, 2>({0, 0}));
    }
    void add(int x) {
        int u = 0;
        for (int i = 29; i >= 0; --i) {
            if (to[u][x >> i & 1] == 0) {
                to.push_back(array <int, 2>({0, 0}));
                to[u][x >> i & 1] = ++sz;
            }
            u = to[u][x >> i & 1];
        }
    }
    int get(int x) {
        if (sz == 0) return -1;
        int u = 0;
        int ans = 0;
        for (int i = 29; i >= 0; --i) {
            if (to[u][x >> i & 1 ^ 1]) {
                ans += (1 << i);
                u = to[u][x >> i & 1 ^ 1];
            } else u = to[u][x >> i & 1];
        }
        return ans;
    }
};

int q;
vector <pair <int, int> > e[Nmax];
int in[Nmax], out[Nmax], ti, d[Nmax];

void dfs(int u) {
    in[u] = ++ti;
    for (auto [v, w]: e[u]) {
        d[v] = d[u] ^ w;
        dfs(v);
    }
    out[u] = ti;
}

Trie st[Nmax * 4];

void add(int id, int L, int R, int i, int val) {
    st[id].add(val);
    if (L == R) return;
    int mid = L + R >> 1;
    if (i <= mid) add(id * 2, L, mid, i, val);
    else add(id * 2 + 1, mid + 1, R, i, val);
}

int get(int id, int L, int R, int u, int v, int val) {
    if (u > R || L > v) return -1;
    if (u <= L && R <= v) return st[id].get(val);
    int mid = L + R >> 1;
    return max(get(id * 2, L, mid, u, v, val), get(id * 2 + 1, mid + 1, R, u, v, val));
}

vector <tuple <string, int, int> > queries;

int main() {
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> q;
    int n = 1;
    while (q--) {
        string s;
        int x, y;
        cin >> s >> x >> y;
        if (s == "Add") ++n, e[x].push_back({n, y}), queries.push_back({s, n, y});
        else queries.push_back({s, x, y});
    }
    dfs(1);
    add(1, 1, n, in[1], 0);
    for (auto [s, x, y]: queries) {
        if (s == "Add") add(1, 1, n, in[x], d[x]);
        else cout << get(1, 1, n, in[y], out[y], d[x]) << '\n';
    }
}

Compilation message

klasika.cpp: In member function 'int Trie::get(int)':
klasika.cpp:30:30: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   30 |             if (to[u][x >> i & 1 ^ 1]) {
      |                       ~~~~~~~^~~
klasika.cpp:32:34: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   32 |                 u = to[u][x >> i & 1 ^ 1];
      |                           ~~~~~~~^~~
klasika.cpp: In function 'void dfs(int)':
klasika.cpp:45:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |     for (auto [v, w]: e[u]) {
      |               ^
klasika.cpp: In function 'void add(int, int, int, int, int)':
klasika.cpp:57:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     int mid = L + R >> 1;
      |               ~~^~~
klasika.cpp: In function 'int get(int, int, int, int, int, int)':
klasika.cpp:65:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |     int mid = L + R >> 1;
      |               ~~^~~
klasika.cpp: In function 'int main()':
klasika.cpp:84:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |     for (auto [s, x, y]: queries) {
      |               ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 55108 KB Output is correct
2 Correct 63 ms 55164 KB Output is correct
3 Correct 56 ms 55388 KB Output is correct
4 Correct 58 ms 55444 KB Output is correct
5 Correct 55 ms 55108 KB Output is correct
6 Correct 55 ms 55192 KB Output is correct
7 Correct 56 ms 55376 KB Output is correct
8 Correct 55 ms 55536 KB Output is correct
9 Correct 55 ms 55228 KB Output is correct
10 Correct 55 ms 55312 KB Output is correct
11 Correct 55 ms 55364 KB Output is correct
12 Correct 57 ms 55492 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 55108 KB Output is correct
2 Correct 63 ms 55164 KB Output is correct
3 Correct 56 ms 55388 KB Output is correct
4 Correct 58 ms 55444 KB Output is correct
5 Correct 55 ms 55108 KB Output is correct
6 Correct 55 ms 55192 KB Output is correct
7 Correct 56 ms 55376 KB Output is correct
8 Correct 55 ms 55536 KB Output is correct
9 Correct 55 ms 55228 KB Output is correct
10 Correct 55 ms 55312 KB Output is correct
11 Correct 55 ms 55364 KB Output is correct
12 Correct 57 ms 55492 KB Output is correct
13 Correct 59 ms 56360 KB Output is correct
14 Correct 61 ms 57576 KB Output is correct
15 Correct 63 ms 58820 KB Output is correct
16 Correct 67 ms 60544 KB Output is correct
17 Correct 58 ms 56336 KB Output is correct
18 Correct 60 ms 57612 KB Output is correct
19 Correct 64 ms 58600 KB Output is correct
20 Correct 64 ms 60132 KB Output is correct
21 Correct 57 ms 56260 KB Output is correct
22 Correct 66 ms 57492 KB Output is correct
23 Correct 63 ms 58624 KB Output is correct
24 Correct 65 ms 60160 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 511 ms 211296 KB Output is correct
2 Correct 851 ms 372332 KB Output is correct
3 Runtime error 1148 ms 524292 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 55108 KB Output is correct
2 Correct 63 ms 55164 KB Output is correct
3 Correct 56 ms 55388 KB Output is correct
4 Correct 58 ms 55444 KB Output is correct
5 Correct 55 ms 55108 KB Output is correct
6 Correct 55 ms 55192 KB Output is correct
7 Correct 56 ms 55376 KB Output is correct
8 Correct 55 ms 55536 KB Output is correct
9 Correct 55 ms 55228 KB Output is correct
10 Correct 55 ms 55312 KB Output is correct
11 Correct 55 ms 55364 KB Output is correct
12 Correct 57 ms 55492 KB Output is correct
13 Correct 59 ms 56360 KB Output is correct
14 Correct 61 ms 57576 KB Output is correct
15 Correct 63 ms 58820 KB Output is correct
16 Correct 67 ms 60544 KB Output is correct
17 Correct 58 ms 56336 KB Output is correct
18 Correct 60 ms 57612 KB Output is correct
19 Correct 64 ms 58600 KB Output is correct
20 Correct 64 ms 60132 KB Output is correct
21 Correct 57 ms 56260 KB Output is correct
22 Correct 66 ms 57492 KB Output is correct
23 Correct 63 ms 58624 KB Output is correct
24 Correct 65 ms 60160 KB Output is correct
25 Correct 511 ms 211296 KB Output is correct
26 Correct 851 ms 372332 KB Output is correct
27 Runtime error 1148 ms 524292 KB Execution killed with signal 9
28 Halted 0 ms 0 KB -