oj.uz

Submission #872654

# Submission time Handle Problem Language Result Execution time Memory
872654 2023-11-13T13:44:39 Z vjudge1 Klasika (COCI20_klasika) C++17
0 / 110
 60 ms 38484 KB 
#include<bits/stdc++.h>
#ifdef LOCAL
#include "Essentials/algo/debug.h"
#else
#define debug(...) 69
#endif
using namespace std;

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

const int N = 2e5 + 23;
const int LOG = 31;
const ll inf = 1e18;

#define F           first
#define S           second
#define pb          push_back
#define kill(x)     cout<<x<<endl, exit(0);
#define all(x)      x.begin(),x.end()
#define sz(x)       (int)x.size()
#define lc          (v << 1)
#define rc          ((v<<1) |1)

int st[N],ft[N];
int timer =1;
vector<int> G[N];

void dfsset(int v) {
	st[v] = timer ++;
	for(int u : G[v]) dfsset(u);
	ft[v] = timer-1;
}

struct node {
	node* ch[2];
	set<int> s;
	
	node() {
		ch[0] = ch[1] = nullptr;
	}
}root;

int val[N];

void add(int v) {
	int x = val[v];
	node* cur = &root;
	for(int i = LOG-1; i >= 0 ; i --) {
		int p = (x >> i)&1;
		if(cur->ch[p] == nullptr) {
			cur->ch[p] = new node();
		}
		cur = cur->ch[p];
		cur->s.insert(st[v]);
	}
}

int get(int v,int x) {
	node* cur = &root;
	int ans=0;
	for(int i = LOG-1; i >= 0 ; i --) {
		int p = (x >> i)&1;
		p ^= 1;
		if(cur->ch[p] != nullptr) {
			auto itr = cur->ch[p]->s.lower_bound(st[v]);
			debug(v,st[v],ft[v],  cur->ch[p]->s,*itr);
			if(itr != cur->ch[p]->s.end() && (*itr) <= ft[v]) {
				cur = cur->ch[p];
				ans |= (1 << i);
			} else {
				p ^= 1;
				cur = cur->ch[p];
			}
		} else {
			p ^= 1;
			cur = cur->ch[p];
		}
	}	
	return ans;
}

int q;
vector<pair<string,pii>> que;

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
	cin>>q;
	int n = 1;
	for(int i = 0 ;i < q; i++) {
		string s; int a,b; cin>>s>>a>>b;
		if(s == "Add") {
			G[a].pb(++n);
			val[n] = val[a] ^ b;
		}
		que.pb({s,{a,b}});
	}
	dfsset(1);
	n = 1;
	debug(que);
	for(auto [s,qq] : que) {
		auto [a,b] = qq;
		if(s == "Add") {
			add(++n);
		} else {
			cout<<get(b,val[a]) << '\n';
		}
	}
	return 0;
}

Compilation message

klasika.cpp: In function 'int get(int, int)':
klasika.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
klasika.cpp:67:4: note: in expansion of macro 'debug'
   67 |    debug(v,st[v],ft[v],  cur->ch[p]->s,*itr);
      |    ^~~~~
klasika.cpp: In function 'int32_t main()':
klasika.cpp:5:20: warning: statement has no effect [-Wunused-value]
    5 | #define debug(...) 69
      |                    ^~
klasika.cpp:100:2: note: in expansion of macro 'debug'
  100 |  debug(que);
      |  ^~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 12892 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 8 ms 12892 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

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

Subtask #4
0 / 44.0

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