oj.uz

Submission #229232

# Submission time Handle Problem Language Result Execution time Memory
229232 2020-05-03T21:17:41 Z VEGAnn Klasika (COCI20_klasika) C++14
110 / 110
 417 ms 70776 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define ft first
#define sd second
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
const int N = 200100;
const int PW = 31;
const int M = PW * N;
const int K = 10010;
const int oo = 2e9;
vector<pii> qr[N];
vector<int> g[N];
string qur;
int ans[N], pr[N], xr[N], koli, siz[N], lst = 1, net[M][2], kol[M], tim[N], mn[M], n, q;
bool typ[N];
 
void build_sz(int v){
    siz[v] = 1;
    
    for (int u : g[v]){
        build_sz(u);
        siz[v] += siz[u];
    }
}

void insert(int vl, int tm){
    int st = 1;
    
    for (int po = PW - 1; po >= 0; po--){
        int bt = bool(vl & (1 << po));
        
        if (net[st][bt] == 0){
            net[st][bt] = ++lst;
            kol[lst] = 0;
            mn[lst] = tm;
        }
        
        st = net[st][bt];
        mn[st] = min(mn[st], tm);
        kol[st]++;
    }
}

void CLEAR(){
    for (int i = 1; i <= lst; i++){
        net[i][0] = net[i][1] = 0;
    }
    lst = 1;
}

void insert_dfs(int v){
    insert(xr[v], tim[v]);
    
    for (int u : g[v])
        insert_dfs(u);
}

int answer(int mx_tim, int vl){
    int res = 0, st = 1;
    
    for (int po = PW - 1; po >= 0; po--){
        int bt = bool(vl & (1 << po));
        
        if (net[st][bt ^ 1] != 0 && mn[net[st][bt ^ 1]] <= mx_tim){
            res += (1 << po);
            st = net[st][bt ^ 1];
        } else st = net[st][bt];
    }
    
    return res;
}

void dfs(int v, bool mrk){
    int mx = -1, nom = -1;
    
    for (int u : g[v])
        if (siz[u] > mx){
            mx = siz[u];
            nom = u;
        }
        
    if (mx < 0){
        for (pii cr : qr[v])
            ans[cr.ft] = xr[cr.sd] ^ xr[v];
        
        if (mrk){
            insert(xr[v], tim[v]);
        } 
    } else {
        
        for (int u : g[v])
            if (u != nom)
                dfs(u, 0);
        
        dfs(nom, 1);
        
        insert(xr[v], tim[v]);
        
        for (int u : g[v])
            if (u != nom)
                insert_dfs(u);
            
        for (pii cr : qr[v])
            ans[cr.ft] = answer(cr.ft, xr[cr.sd]);
    }
    
    if (!mrk)
        CLEAR();
}
 
int main(){
    
    ios_base::sync_with_stdio(0); cin.tie(0);
    
//    freopen("in.txt","r",stdin);

    cin >> q;
    
    tim[0] = -1;
    pr[0] = -1;
    xr[0] = 0;
    koli = 1;
    
    for (int i = 0; i < q; i++){
        cin >> qur;
        
        if (qur[0] == 'Q'){
            typ[i] = 1;
            int x, y; cin >> x >> y;
            x--; y--;
            
            qr[y].PB(MP(i, x));
        } else {
            
            int x, y; cin >> x >> y;
            x--;
            
            tim[koli] = i;
            pr[koli] = x;
            xr[koli] = xr[x] ^ y;
            g[x].PB(koli);
            koli++;
        }
    }
    
    build_sz(0);
    
    dfs(0, 0);
    
    for (int i = 0; i < q; i++)
        if (typ[i])
            cout << ans[i] << '\n';
  
    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9856 KB Output is correct
2 Correct 11 ms 9856 KB Output is correct
3 Correct 10 ms 9856 KB Output is correct
4 Correct 11 ms 9856 KB Output is correct
5 Correct 10 ms 9856 KB Output is correct
6 Correct 10 ms 9856 KB Output is correct
7 Correct 10 ms 9856 KB Output is correct
8 Correct 10 ms 9856 KB Output is correct
9 Correct 10 ms 9856 KB Output is correct
10 Correct 10 ms 9856 KB Output is correct
11 Correct 10 ms 9856 KB Output is correct
12 Correct 10 ms 9856 KB Output is correct
13 Correct 11 ms 10112 KB Output is correct
14 Correct 12 ms 10240 KB Output is correct
15 Correct 12 ms 10496 KB Output is correct
16 Correct 12 ms 10624 KB Output is correct
17 Correct 11 ms 9984 KB Output is correct
18 Correct 12 ms 10240 KB Output is correct
19 Correct 12 ms 10368 KB Output is correct
20 Correct 14 ms 10496 KB Output is correct
21 Correct 11 ms 10112 KB Output is correct
22 Correct 11 ms 10240 KB Output is correct
23 Correct 13 ms 10368 KB Output is correct
24 Correct 12 ms 10496 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 31460 KB Output is correct
2 Correct 181 ms 44780 KB Output is correct
3 Correct 204 ms 57320 KB Output is correct
4 Correct 210 ms 70000 KB Output is correct
5 Correct 185 ms 27820 KB Output is correct
6 Correct 259 ms 37356 KB Output is correct
7 Correct 360 ms 46188 KB Output is correct
8 Correct 380 ms 54900 KB Output is correct
9 Correct 154 ms 28472 KB Output is correct
10 Correct 195 ms 38760 KB Output is correct
11 Correct 238 ms 48364 KB Output is correct
12 Correct 227 ms 57784 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9856 KB Output is correct
2 Correct 11 ms 9856 KB Output is correct
3 Correct 10 ms 9856 KB Output is correct
4 Correct 11 ms 9856 KB Output is correct
5 Correct 10 ms 9856 KB Output is correct
6 Correct 10 ms 9856 KB Output is correct
7 Correct 10 ms 9856 KB Output is correct
8 Correct 10 ms 9856 KB Output is correct
9 Correct 10 ms 9856 KB Output is correct
10 Correct 10 ms 9856 KB Output is correct
11 Correct 10 ms 9856 KB Output is correct
12 Correct 10 ms 9856 KB Output is correct
13 Correct 11 ms 10112 KB Output is correct
14 Correct 12 ms 10240 KB Output is correct
15 Correct 12 ms 10496 KB Output is correct
16 Correct 12 ms 10624 KB Output is correct
17 Correct 11 ms 9984 KB Output is correct
18 Correct 12 ms 10240 KB Output is correct
19 Correct 12 ms 10368 KB Output is correct
20 Correct 14 ms 10496 KB Output is correct
21 Correct 11 ms 10112 KB Output is correct
22 Correct 11 ms 10240 KB Output is correct
23 Correct 13 ms 10368 KB Output is correct
24 Correct 12 ms 10496 KB Output is correct
25 Correct 170 ms 31460 KB Output is correct
26 Correct 181 ms 44780 KB Output is correct
27 Correct 204 ms 57320 KB Output is correct
28 Correct 210 ms 70000 KB Output is correct
29 Correct 185 ms 27820 KB Output is correct
30 Correct 259 ms 37356 KB Output is correct
31 Correct 360 ms 46188 KB Output is correct
32 Correct 380 ms 54900 KB Output is correct
33 Correct 154 ms 28472 KB Output is correct
34 Correct 195 ms 38760 KB Output is correct
35 Correct 238 ms 48364 KB Output is correct
36 Correct 227 ms 57784 KB Output is correct
37 Correct 208 ms 32968 KB Output is correct
38 Correct 239 ms 46200 KB Output is correct
39 Correct 243 ms 58872 KB Output is correct
40 Correct 231 ms 70776 KB Output is correct
41 Correct 183 ms 29176 KB Output is correct
42 Correct 248 ms 38648 KB Output is correct
43 Correct 311 ms 47608 KB Output is correct
44 Correct 417 ms 55664 KB Output is correct
45 Correct 156 ms 29688 KB Output is correct
46 Correct 187 ms 40056 KB Output is correct
47 Correct 211 ms 49528 KB Output is correct
48 Correct 229 ms 58616 KB Output is correct