oj.uz

Submission #1110385

# Submission time Handle Problem Language Result Execution time Memory
1110385 2024-11-09T11:13:36 Z flyingkite Klasika (COCI20_klasika) C++17
110 / 110
 2348 ms 515408 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 3e6 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 450;
ll n = 1, q, timer = 0;
vector<pll>adj[N];
struct query{ll typ,x,y;} t[N];
ll tin[N], tout[N], dep[N];
void dfs(ll u, ll par){
    tin[u] = ++timer;
    for(auto v : adj[u]){
        if(v.F == par) continue;
        dep[v.F] = dep[u] ^ v.S;
        dfs(v.F, u);
    }
    tout[u] = timer;
}
struct Trie{
    struct ccjv{
        ll c[2]; set<ll>s;
    } t[N];
    ll cur = 3e6;
    void init(){
        for(int i = 0; i <= cur;i++) t[i].c[0] = t[i].c[1] = -1, t[i].s.clear();
        cur = 0;
    }
    void add(ll x, ll val){
        ll pos = 0;
        for(int i = 30; i >= 0;i--){
            ll f = (x >> i) & 1;
            if(t[pos].c[f] == -1) t[pos].c[f] = ++cur;
            pos = t[pos].c[f];
            t[pos].s.insert(val);
        }
    }
    bool ok(ll pos, ll l, ll r){
        auto it = t[pos].s.lower_bound(l);
        if(it == t[pos].s.end() || (*it > r)) return 0;
        return 1;
    }
    ll query(ll x, ll l, ll r){
        ll pos = 0, res = 0;
        for(int i = 30; i >= 0;i--){
            ll f = (x >> i) & 1;
            if(t[pos].c[f ^ 1] != -1 && ok(t[pos].c[f ^ 1], l, r)){
                res |= (1 << i);
                pos = t[pos].c[f ^ 1];
            }
            else if(t[pos].c[f] != -1 && ok(t[pos].c[f], l, r)) pos = t[pos].c[f];
        }
        return res;
    }
} chinsu;
void to_thic_cau(){
    cin >> q;
    for(int i = 1; i <= q;i++){
        string s; ll x,y; cin >> s >> x >> y;
        if(s == "Add") adj[x].pb({++n, y}), t[i] = {1, n, x};      
        else t[i] = {2, x, y};
    }
    dfs(1, 0);
    chinsu.init();
    chinsu.add(0, 1);
    for(int i = 1; i <= q;i++){
        if(t[i].typ == 1) {
            chinsu.add(dep[t[i].x], tin[t[i].x]);
        }
        else{
            cout << chinsu.query(dep[t[i].x], tin[t[i].y], tout[t[i].y]) << '\n';
        }
    }
}    
 
signed main()   
{  
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll tc = 1;
    //cin >> tc;
    while(tc--) to_thic_cau();
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 266236 KB Output is correct
2 Correct 58 ms 266312 KB Output is correct
3 Correct 54 ms 266312 KB Output is correct
4 Correct 56 ms 266528 KB Output is correct
5 Correct 61 ms 264264 KB Output is correct
6 Correct 53 ms 259092 KB Output is correct
7 Correct 54 ms 262280 KB Output is correct
8 Correct 54 ms 259344 KB Output is correct
9 Correct 56 ms 260180 KB Output is correct
10 Correct 64 ms 259144 KB Output is correct
11 Correct 71 ms 265292 KB Output is correct
12 Correct 68 ms 259144 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 266236 KB Output is correct
2 Correct 58 ms 266312 KB Output is correct
3 Correct 54 ms 266312 KB Output is correct
4 Correct 56 ms 266528 KB Output is correct
5 Correct 61 ms 264264 KB Output is correct
6 Correct 53 ms 259092 KB Output is correct
7 Correct 54 ms 262280 KB Output is correct
8 Correct 54 ms 259344 KB Output is correct
9 Correct 56 ms 260180 KB Output is correct
10 Correct 64 ms 259144 KB Output is correct
11 Correct 71 ms 265292 KB Output is correct
12 Correct 68 ms 259144 KB Output is correct
13 Correct 75 ms 259792 KB Output is correct
14 Correct 77 ms 260256 KB Output is correct
15 Correct 84 ms 260880 KB Output is correct
16 Correct 83 ms 261604 KB Output is correct
17 Correct 79 ms 259532 KB Output is correct
18 Correct 87 ms 260200 KB Output is correct
19 Correct 83 ms 260932 KB Output is correct
20 Correct 86 ms 261448 KB Output is correct
21 Correct 82 ms 266832 KB Output is correct
22 Correct 57 ms 267344 KB Output is correct
23 Correct 59 ms 263828 KB Output is correct
24 Correct 57 ms 261544 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 329288 KB Output is correct
2 Correct 924 ms 389624 KB Output is correct
3 Correct 1365 ms 452588 KB Output is correct
4 Correct 1710 ms 512956 KB Output is correct
5 Correct 536 ms 326216 KB Output is correct
6 Correct 1006 ms 385680 KB Output is correct
7 Correct 1587 ms 446824 KB Output is correct
8 Correct 2020 ms 504840 KB Output is correct
9 Correct 497 ms 325432 KB Output is correct
10 Correct 872 ms 386968 KB Output is correct
11 Correct 1250 ms 446824 KB Output is correct
12 Correct 1604 ms 506600 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 266236 KB Output is correct
2 Correct 58 ms 266312 KB Output is correct
3 Correct 54 ms 266312 KB Output is correct
4 Correct 56 ms 266528 KB Output is correct
5 Correct 61 ms 264264 KB Output is correct
6 Correct 53 ms 259092 KB Output is correct
7 Correct 54 ms 262280 KB Output is correct
8 Correct 54 ms 259344 KB Output is correct
9 Correct 56 ms 260180 KB Output is correct
10 Correct 64 ms 259144 KB Output is correct
11 Correct 71 ms 265292 KB Output is correct
12 Correct 68 ms 259144 KB Output is correct
13 Correct 75 ms 259792 KB Output is correct
14 Correct 77 ms 260256 KB Output is correct
15 Correct 84 ms 260880 KB Output is correct
16 Correct 83 ms 261604 KB Output is correct
17 Correct 79 ms 259532 KB Output is correct
18 Correct 87 ms 260200 KB Output is correct
19 Correct 83 ms 260932 KB Output is correct
20 Correct 86 ms 261448 KB Output is correct
21 Correct 82 ms 266832 KB Output is correct
22 Correct 57 ms 267344 KB Output is correct
23 Correct 59 ms 263828 KB Output is correct
24 Correct 57 ms 261544 KB Output is correct
25 Correct 581 ms 329288 KB Output is correct
26 Correct 924 ms 389624 KB Output is correct
27 Correct 1365 ms 452588 KB Output is correct
28 Correct 1710 ms 512956 KB Output is correct
29 Correct 536 ms 326216 KB Output is correct
30 Correct 1006 ms 385680 KB Output is correct
31 Correct 1587 ms 446824 KB Output is correct
32 Correct 2020 ms 504840 KB Output is correct
33 Correct 497 ms 325432 KB Output is correct
34 Correct 872 ms 386968 KB Output is correct
35 Correct 1250 ms 446824 KB Output is correct
36 Correct 1604 ms 506600 KB Output is correct
37 Correct 1002 ms 337480 KB Output is correct
38 Correct 1366 ms 389448 KB Output is correct
39 Correct 1768 ms 451976 KB Output is correct
40 Correct 2029 ms 513156 KB Output is correct
41 Correct 1098 ms 325448 KB Output is correct
42 Correct 1540 ms 385492 KB Output is correct
43 Correct 1989 ms 444820 KB Output is correct
44 Correct 2348 ms 504616 KB Output is correct
45 Correct 1286 ms 325164 KB Output is correct
46 Correct 1766 ms 386336 KB Output is correct
47 Correct 1949 ms 453448 KB Output is correct
48 Correct 1983 ms 515408 KB Output is correct