oj.uz

Submission #889422

# Submission time Handle Problem Language Result Execution time Memory
889422 2023-12-19T16:11:26 Z Alish Klasika (COCI20_klasika) C++17
33 / 110
 1947 ms 423492 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("in.txt" , "r" , stdin) ; freopen("out.txt" , "w" , stdout);


ll mod = 1e9+7 ;

const int N = 2e5+23, L=31;


int h[N];
struct node {
	node* ch[2];
	set<int> ss;

	node() {
		ch[0] = ch[1] = nullptr;
	}
}root;

int st[N], ft[N], tim=0;
vector<int> g[N];
vector<pair<int, pii> > Q;
int cnt=1;
int tr;

void dfs(int v){
    st[v]=tim++;
    for (int u: g[v]) dfs(u);
    ft[v]=tim;
}

void add(int x, int pp){
    node* cur=&root;

    for (int i=L-1; i>=0; i--){
        int t=(x>>i&1);
        if(cur->ch[t]==nullptr) cur->ch[t]= new node();

        cur=cur->ch[t];
        cur->ss.insert(pp);
    }
}

int get(int x, int v){
    node* cur=&root;
    int ans=0;
    for (int i=L-1; i>=0; i--){
        int t=(x>>i&1);
        t=1-t;
        if(cur->ch[t]!=nullptr){
            auto x=cur->ss.lower_bound(st[v]);

            if(x==cur->ss.end() || *x>=ft[v]){
                cur=cur->ch[1-t];
            }
            else{
                ans+=(1<<i);
                cur=cur->ch[t];
            }
        }
        else{
            cur=cur->ch[1-t];
        }
    }
    return ans;
}

int main()
{
    //fast_io
    int q; cin>>q;
    for (int i=0; i<q; i++){
        string s; cin>>s;
        if(s=="Add"){
             ll u, w;
            cin>>u>>w;
            cnt++;
            h[cnt]=h[u]^w;
            g[u].pb(cnt);
            Q.pb({0, {cnt, u}});
        }
        else{
                int u, v; cin>>v>>u;
            Q.pb({1, {v, u}});
        }
    }
    dfs(1);

    for (int i=0; i<=cnt; i++){
        g[i].clear();
        g[i].shrink_to_fit();
    }
    add(0, st[1]);

    for (auto pp: Q){
        int t=pp.F, v=pp.S.F, u=pp.S.S;
        if(!t){
            add(h[v], st[v]);
        }
        else{
            cout<<get(h[v], u)<<endl;
        }
    }

}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 13404 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 13404 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 119020 KB Output is correct
2 Correct 889 ms 221984 KB Output is correct
3 Correct 1265 ms 320824 KB Output is correct
4 Correct 1686 ms 423492 KB Output is correct
5 Correct 613 ms 121244 KB Output is correct
6 Correct 995 ms 223736 KB Output is correct
7 Correct 1451 ms 322384 KB Output is correct
8 Correct 1947 ms 419820 KB Output is correct
9 Correct 558 ms 120660 KB Output is correct
10 Correct 941 ms 223876 KB Output is correct
11 Correct 1258 ms 324192 KB Output is correct
12 Correct 1688 ms 420896 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 13404 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -