oj.uz

Submission #198512

# Submission time Handle Problem Language Result Execution time Memory
198512 2020-01-26T12:45:19 Z alishahali1382 Klasika (COCI20_klasika) C++14
33 / 110
 3516 ms 524292 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define get(x, y) (((x)>>(y))&1)
 
const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 200010, LOG=31;
 
int n=1, m, k, u, v, x, y, t, L, R, X, ans;
int TR[MAXN*LOG][2], ts;
int par[MAXN], val[MAXN];
int stt[MAXN], fnt[MAXN], timer;
int typ[MAXN], A[MAXN], B[MAXN];
vector<int> G[MAXN];
set<int> vec[MAXN*LOG];
string s;

bool f(int v, int l, int r){
    auto it=vec[v].lower_bound(l);
    if (it==vec[v].end() || r<=*it) return 0;
    return 1;
}
 
void dfs(int node){
    stt[node]=timer++;
    for (int v:G[node]) dfs(v);
    fnt[node]=timer;
}
 
void Add(int X, int pos){
    int v=0;
    for (int i=LOG-1; ~i; i--){
        int c=get(X, i);
        if (!TR[v][c]) TR[v][c]=++ts;
        v=TR[v][c];
        vec[v].insert(pos);
    }
}
 
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin>>m;
    for (int i=1; i<=m; i++){
        cin>>s>>A[i]>>B[i];
        if (s=="Add"){
            par[++n]=A[i];
            val[n]=val[A[i]]^B[i];
            G[A[i]].pb(n);
            continue ;
        }
        typ[i]=1;
    }
    dfs(1);
    n=1;
    Add(0, stt[1]);
    
    for (int i=1; i<=m; i++){
        if (typ[i]){
            X=val[A[i]];    
            L=stt[B[i]];
            R=fnt[B[i]];
            ans=0;
            
            int v=0;
            for (int i=LOG-1; ~i; i--){
                int c=get(X, i)^1;
                if (TR[v][c] && f(TR[v][c], L, R)) ans|=(1<<i);
                else c^=1;
                v=TR[v][c];
            }
            
            cout<<ans<<'\n';
            continue ;
        }
        ++n;
        Add(val[n], stt[n]);
    }
    
    
    
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 296440 KB Output is correct
2 Correct 175 ms 296440 KB Output is correct
3 Correct 176 ms 296568 KB Output is correct
4 Correct 175 ms 296568 KB Output is correct
5 Correct 175 ms 296312 KB Output is correct
6 Correct 172 ms 296440 KB Output is correct
7 Correct 179 ms 296568 KB Output is correct
8 Correct 173 ms 296568 KB Output is correct
9 Correct 176 ms 296436 KB Output is correct
10 Correct 173 ms 296444 KB Output is correct
11 Correct 175 ms 296568 KB Output is correct
12 Correct 178 ms 296568 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 296440 KB Output is correct
2 Correct 175 ms 296440 KB Output is correct
3 Correct 176 ms 296568 KB Output is correct
4 Correct 175 ms 296568 KB Output is correct
5 Correct 175 ms 296312 KB Output is correct
6 Correct 172 ms 296440 KB Output is correct
7 Correct 179 ms 296568 KB Output is correct
8 Correct 173 ms 296568 KB Output is correct
9 Correct 176 ms 296436 KB Output is correct
10 Correct 173 ms 296444 KB Output is correct
11 Correct 175 ms 296568 KB Output is correct
12 Correct 178 ms 296568 KB Output is correct
13 Correct 177 ms 297080 KB Output is correct
14 Correct 175 ms 297720 KB Output is correct
15 Correct 181 ms 298372 KB Output is correct
16 Correct 177 ms 299132 KB Output is correct
17 Correct 175 ms 296956 KB Output is correct
18 Correct 176 ms 297592 KB Output is correct
19 Correct 194 ms 298336 KB Output is correct
20 Correct 184 ms 299000 KB Output is correct
21 Correct 178 ms 296952 KB Output is correct
22 Correct 178 ms 297720 KB Output is correct
23 Correct 180 ms 298360 KB Output is correct
24 Correct 182 ms 299000 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1051 ms 367140 KB Output is correct
2 Correct 1840 ms 433272 KB Output is correct
3 Correct 3227 ms 498044 KB Output is correct
4 Runtime error 3516 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 296440 KB Output is correct
2 Correct 175 ms 296440 KB Output is correct
3 Correct 176 ms 296568 KB Output is correct
4 Correct 175 ms 296568 KB Output is correct
5 Correct 175 ms 296312 KB Output is correct
6 Correct 172 ms 296440 KB Output is correct
7 Correct 179 ms 296568 KB Output is correct
8 Correct 173 ms 296568 KB Output is correct
9 Correct 176 ms 296436 KB Output is correct
10 Correct 173 ms 296444 KB Output is correct
11 Correct 175 ms 296568 KB Output is correct
12 Correct 178 ms 296568 KB Output is correct
13 Correct 177 ms 297080 KB Output is correct
14 Correct 175 ms 297720 KB Output is correct
15 Correct 181 ms 298372 KB Output is correct
16 Correct 177 ms 299132 KB Output is correct
17 Correct 175 ms 296956 KB Output is correct
18 Correct 176 ms 297592 KB Output is correct
19 Correct 194 ms 298336 KB Output is correct
20 Correct 184 ms 299000 KB Output is correct
21 Correct 178 ms 296952 KB Output is correct
22 Correct 178 ms 297720 KB Output is correct
23 Correct 180 ms 298360 KB Output is correct
24 Correct 182 ms 299000 KB Output is correct
25 Correct 1051 ms 367140 KB Output is correct
26 Correct 1840 ms 433272 KB Output is correct
27 Correct 3227 ms 498044 KB Output is correct
28 Runtime error 3516 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -