oj.uz

Submission #872656

# Submission time Handle Problem Language Result Execution time Memory
872656 2023-11-13T13:50:07 Z vjudge1 Klasika (COCI20_klasika) C++17
33 / 110
 1948 ms 435936 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;
}

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);
	add(1);
	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 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Incorrect 1 ms 6748 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Incorrect 1 ms 6748 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 126972 KB Output is correct
2 Correct 921 ms 233872 KB Output is correct
3 Correct 1270 ms 335076 KB Output is correct
4 Correct 1733 ms 435936 KB Output is correct
5 Correct 544 ms 127408 KB Output is correct
6 Correct 991 ms 232584 KB Output is correct
7 Correct 1484 ms 329936 KB Output is correct
8 Correct 1948 ms 428880 KB Output is correct
9 Correct 563 ms 128184 KB Output is correct
10 Correct 916 ms 233148 KB Output is correct
11 Correct 1273 ms 332468 KB Output is correct
12 Correct 1646 ms 430868 KB Output is correct

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 7004 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Incorrect 1 ms 6748 KB Output isn't correct
6 Halted 0 ms 0 KB -