oj.uz

Submission #328461

# Submission time Handle Problem Language Result Execution time Memory
328461 2020-11-16T16:50:21 Z BeanZ Klasika (COCI20_klasika) C++14
110 / 110
 3240 ms 429640 KB 
// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define endl '\n'
const int N = 2e5 + 5;
const int mod = 123456789;
const long long oo = 1e18;
ll timer = 1, timer2 = 0, timer3 = 1;
ll cost[N], tin[N], tout[N], dp[N * 16][2];
vector<ll> node[N];
set<ll> mem[N * 16];
void dfs(ll u){
    timer2++;
    tin[u] = timer2;
    for (auto j : node[u]){
        dfs(j);
    }
    tout[u] = timer2;
}
void add(ll u, ll p){
    ll now = 1;
    for (int i = 30; i >= 0; i--){
        ll a = ((u & (1 << i)) > 0);
        if (dp[now][a] == 0){
            timer3++;
            dp[now][a] = timer3;
        }
        now = dp[now][a];
        mem[now].insert(p);
    }
}
ll get(ll u, ll l, ll r){
    ll now = 1;
    ll res = 0;
    for (int i = 30; i >= 0; i--){
        ll a = ((u & (1 << i)) > 0);
        ll id = dp[now][1 - a];
        bool flag = true;
        auto it = mem[id].lower_bound(l);
        if (it == mem[id].end() || (*it) > r) flag = false;
        if (flag){
            res = res + (1 << i);
            now = id;
        } else {
            now = dp[now][a];
        }
        /*
        if (u == 0){
            if (it == mem[id].end()) cout << -1 << " ";
            else cout << (*it) << " ";
            cout << id << " ";
        }*/
    }
    //cout << now << " " << res << endl;
    return res;
}
string task[N];
ll x[N], y[N];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("A.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll q;
    cin >> q;
    for (int i = 1; i <= q; i++){
        cin >> task[i];
        if (task[i] == "Add"){
            cin >> x[i] >> y[i];
            timer++;
            cost[timer] = cost[x[i]] ^ y[i];
            node[x[i]].push_back(timer);
            x[i] = timer;
        } else {
            cin >> x[i] >> y[i];
        }
    }
    dfs(1);
    add(0, tin[1]);
    for (int i = 1; i <= q; i++){
        if (task[i] == "Add"){
            add(cost[x[i]], tin[x[i]]);
        } else {
            cout << get(cost[x[i]], tin[y[i]], tout[y[i]]) << endl;
        }
    }
    //cout << dp[1][0] << endl;
}
/*
3
Add 1 9
Add 2 3
Query 1 2
*/

Compilation message

klasika.cpp: In function 'int main()':
klasika.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   64 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
klasika.cpp:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   65 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 161772 KB Output is correct
2 Correct 105 ms 161900 KB Output is correct
3 Correct 103 ms 161772 KB Output is correct
4 Correct 108 ms 161900 KB Output is correct
5 Correct 107 ms 161636 KB Output is correct
6 Correct 103 ms 161772 KB Output is correct
7 Correct 104 ms 161772 KB Output is correct
8 Correct 102 ms 161900 KB Output is correct
9 Correct 104 ms 161772 KB Output is correct
10 Correct 107 ms 161900 KB Output is correct
11 Correct 103 ms 161900 KB Output is correct
12 Correct 103 ms 161900 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 161772 KB Output is correct
2 Correct 105 ms 161900 KB Output is correct
3 Correct 103 ms 161772 KB Output is correct
4 Correct 108 ms 161900 KB Output is correct
5 Correct 107 ms 161636 KB Output is correct
6 Correct 103 ms 161772 KB Output is correct
7 Correct 104 ms 161772 KB Output is correct
8 Correct 102 ms 161900 KB Output is correct
9 Correct 104 ms 161772 KB Output is correct
10 Correct 107 ms 161900 KB Output is correct
11 Correct 103 ms 161900 KB Output is correct
12 Correct 103 ms 161900 KB Output is correct
13 Correct 105 ms 162412 KB Output is correct
14 Correct 111 ms 163052 KB Output is correct
15 Correct 117 ms 163820 KB Output is correct
16 Correct 110 ms 164332 KB Output is correct
17 Correct 106 ms 162284 KB Output is correct
18 Correct 113 ms 163052 KB Output is correct
19 Correct 109 ms 163692 KB Output is correct
20 Correct 110 ms 164332 KB Output is correct
21 Correct 117 ms 162412 KB Output is correct
22 Correct 110 ms 163052 KB Output is correct
23 Correct 108 ms 163692 KB Output is correct
24 Correct 113 ms 164332 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 989 ms 231312 KB Output is correct
2 Correct 1590 ms 296940 KB Output is correct
3 Correct 2137 ms 360912 KB Output is correct
4 Correct 2746 ms 429284 KB Output is correct
5 Correct 976 ms 232060 KB Output is correct
6 Correct 1642 ms 296284 KB Output is correct
7 Correct 2280 ms 358972 KB Output is correct
8 Correct 2941 ms 422276 KB Output is correct
9 Correct 966 ms 231916 KB Output is correct
10 Correct 1596 ms 296984 KB Output is correct
11 Correct 2236 ms 360836 KB Output is correct
12 Correct 2848 ms 424008 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 161772 KB Output is correct
2 Correct 105 ms 161900 KB Output is correct
3 Correct 103 ms 161772 KB Output is correct
4 Correct 108 ms 161900 KB Output is correct
5 Correct 107 ms 161636 KB Output is correct
6 Correct 103 ms 161772 KB Output is correct
7 Correct 104 ms 161772 KB Output is correct
8 Correct 102 ms 161900 KB Output is correct
9 Correct 104 ms 161772 KB Output is correct
10 Correct 107 ms 161900 KB Output is correct
11 Correct 103 ms 161900 KB Output is correct
12 Correct 103 ms 161900 KB Output is correct
13 Correct 105 ms 162412 KB Output is correct
14 Correct 111 ms 163052 KB Output is correct
15 Correct 117 ms 163820 KB Output is correct
16 Correct 110 ms 164332 KB Output is correct
17 Correct 106 ms 162284 KB Output is correct
18 Correct 113 ms 163052 KB Output is correct
19 Correct 109 ms 163692 KB Output is correct
20 Correct 110 ms 164332 KB Output is correct
21 Correct 117 ms 162412 KB Output is correct
22 Correct 110 ms 163052 KB Output is correct
23 Correct 108 ms 163692 KB Output is correct
24 Correct 113 ms 164332 KB Output is correct
25 Correct 989 ms 231312 KB Output is correct
26 Correct 1590 ms 296940 KB Output is correct
27 Correct 2137 ms 360912 KB Output is correct
28 Correct 2746 ms 429284 KB Output is correct
29 Correct 976 ms 232060 KB Output is correct
30 Correct 1642 ms 296284 KB Output is correct
31 Correct 2280 ms 358972 KB Output is correct
32 Correct 2941 ms 422276 KB Output is correct
33 Correct 966 ms 231916 KB Output is correct
34 Correct 1596 ms 296984 KB Output is correct
35 Correct 2236 ms 360836 KB Output is correct
36 Correct 2848 ms 424008 KB Output is correct
37 Correct 1581 ms 234704 KB Output is correct
38 Correct 2187 ms 299724 KB Output is correct
39 Correct 2660 ms 365520 KB Output is correct
40 Correct 3096 ms 429640 KB Output is correct
41 Correct 1712 ms 232576 KB Output is correct
42 Correct 2296 ms 296540 KB Output is correct
43 Correct 2749 ms 359148 KB Output is correct
44 Correct 3208 ms 421924 KB Output is correct
45 Correct 1814 ms 232416 KB Output is correct
46 Correct 2505 ms 297020 KB Output is correct
47 Correct 3054 ms 359876 KB Output is correct
48 Correct 3240 ms 424004 KB Output is correct