oj.uz

Submission #487908

# Submission time Handle Problem Language Result Execution time Memory
487908 2021-11-17T02:28:25 Z hoanghq2004 Klasika (COCI20_klasika) C++14
110 / 110
 2474 ms 466948 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;

int sz;
struct node {
    int to[2];
    set <int> s;
};

vector <node> trie;

void add(int x, int ti) {
    int u = 0;
    for (int i = 29; i >= 0; --i) {
        if (!trie[u].to[x >> i & 1]) {
            trie.push_back(node());
            trie[u].to[x >> i & 1] = trie.size() - 1;
        }
        u = trie[u].to[x >> i & 1];
        trie[u].s.insert(ti);
    }
}

int get(int x, int L, int R) {
    int u = 0;
    int ans = 0;
    for (int i = 29; i >= 0; --i) {
        auto iter = trie[trie[u].to[x >> i & 1 ^ 1]].s.lower_bound(L);
        if (iter == trie[trie[u].to[x >> i & 1 ^ 1]].s.end() || *iter > R) u = trie[u].to[x >> i & 1];
        else ans += (1 << i), u = trie[u].to[x >> i & 1 ^ 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;
}

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

int main() {
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    trie.push_back(node());
    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(d[1], in[1]);
    for (auto [s, x, y]: queries) {
        if (s == "Add") add(d[x], in[x]);
        else cout << get(d[x], in[y], out[y]) << '\n';
    }
}

Compilation message

klasika.cpp: In function 'int get(int, int, int)':
klasika.cpp:33:44: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   33 |         auto iter = trie[trie[u].to[x >> i & 1 ^ 1]].s.lower_bound(L);
      |                                     ~~~~~~~^~~
klasika.cpp:34:44: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   34 |         if (iter == trie[trie[u].to[x >> i & 1 ^ 1]].s.end() || *iter > R) u = trie[u].to[x >> i & 1];
      |                                     ~~~~~~~^~~
klasika.cpp:35:53: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   35 |         else ans += (1 << i), u = trie[u].to[x >> i & 1 ^ 1];
      |                                              ~~~~~~~^~~
klasika.cpp: In function 'void dfs(int)':
klasika.cpp:46:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |     for (auto [v, w]: e[u]) {
      |               ^
klasika.cpp: In function 'int main()':
klasika.cpp:69:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |     for (auto [s, x, y]: queries) {
      |               ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 3 ms 5452 KB Output is correct
5 Correct 2 ms 5068 KB Output is correct
6 Correct 3 ms 5196 KB Output is correct
7 Correct 3 ms 5324 KB Output is correct
8 Correct 3 ms 5452 KB Output is correct
9 Correct 3 ms 5196 KB Output is correct
10 Correct 3 ms 5324 KB Output is correct
11 Correct 3 ms 5324 KB Output is correct
12 Correct 3 ms 5440 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 3 ms 5452 KB Output is correct
5 Correct 2 ms 5068 KB Output is correct
6 Correct 3 ms 5196 KB Output is correct
7 Correct 3 ms 5324 KB Output is correct
8 Correct 3 ms 5452 KB Output is correct
9 Correct 3 ms 5196 KB Output is correct
10 Correct 3 ms 5324 KB Output is correct
11 Correct 3 ms 5324 KB Output is correct
12 Correct 3 ms 5440 KB Output is correct
13 Correct 5 ms 6504 KB Output is correct
14 Correct 7 ms 8068 KB Output is correct
15 Correct 9 ms 8304 KB Output is correct
16 Correct 11 ms 11012 KB Output is correct
17 Correct 6 ms 6504 KB Output is correct
18 Correct 7 ms 7960 KB Output is correct
19 Correct 9 ms 8220 KB Output is correct
20 Correct 9 ms 9120 KB Output is correct
21 Correct 5 ms 6504 KB Output is correct
22 Correct 7 ms 7972 KB Output is correct
23 Correct 8 ms 8220 KB Output is correct
24 Correct 10 ms 9120 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 120320 KB Output is correct
2 Correct 1138 ms 233132 KB Output is correct
3 Correct 1599 ms 283900 KB Output is correct
4 Correct 2114 ms 466948 KB Output is correct
5 Correct 707 ms 118732 KB Output is correct
6 Correct 1239 ms 229660 KB Output is correct
7 Correct 1698 ms 280004 KB Output is correct
8 Correct 2262 ms 460320 KB Output is correct
9 Correct 659 ms 119248 KB Output is correct
10 Correct 1178 ms 230448 KB Output is correct
11 Correct 1641 ms 281768 KB Output is correct
12 Correct 2184 ms 461532 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5196 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 3 ms 5324 KB Output is correct
4 Correct 3 ms 5452 KB Output is correct
5 Correct 2 ms 5068 KB Output is correct
6 Correct 3 ms 5196 KB Output is correct
7 Correct 3 ms 5324 KB Output is correct
8 Correct 3 ms 5452 KB Output is correct
9 Correct 3 ms 5196 KB Output is correct
10 Correct 3 ms 5324 KB Output is correct
11 Correct 3 ms 5324 KB Output is correct
12 Correct 3 ms 5440 KB Output is correct
13 Correct 5 ms 6504 KB Output is correct
14 Correct 7 ms 8068 KB Output is correct
15 Correct 9 ms 8304 KB Output is correct
16 Correct 11 ms 11012 KB Output is correct
17 Correct 6 ms 6504 KB Output is correct
18 Correct 7 ms 7960 KB Output is correct
19 Correct 9 ms 8220 KB Output is correct
20 Correct 9 ms 9120 KB Output is correct
21 Correct 5 ms 6504 KB Output is correct
22 Correct 7 ms 7972 KB Output is correct
23 Correct 8 ms 8220 KB Output is correct
24 Correct 10 ms 9120 KB Output is correct
25 Correct 654 ms 120320 KB Output is correct
26 Correct 1138 ms 233132 KB Output is correct
27 Correct 1599 ms 283900 KB Output is correct
28 Correct 2114 ms 466948 KB Output is correct
29 Correct 707 ms 118732 KB Output is correct
30 Correct 1239 ms 229660 KB Output is correct
31 Correct 1698 ms 280004 KB Output is correct
32 Correct 2262 ms 460320 KB Output is correct
33 Correct 659 ms 119248 KB Output is correct
34 Correct 1178 ms 230448 KB Output is correct
35 Correct 1641 ms 281768 KB Output is correct
36 Correct 2184 ms 461532 KB Output is correct
37 Correct 1175 ms 120644 KB Output is correct
38 Correct 1707 ms 232888 KB Output is correct
39 Correct 2025 ms 285744 KB Output is correct
40 Correct 2356 ms 466764 KB Output is correct
41 Correct 1245 ms 118688 KB Output is correct
42 Correct 1782 ms 229648 KB Output is correct
43 Correct 2118 ms 279504 KB Output is correct
44 Correct 2474 ms 460384 KB Output is correct
45 Correct 1294 ms 119208 KB Output is correct
46 Correct 1866 ms 230184 KB Output is correct
47 Correct 2160 ms 280252 KB Output is correct
48 Correct 2471 ms 461548 KB Output is correct