oj.uz

Submission #872662

# Submission time Handle Problem Language Result Execution time Memory
872662 2023-11-13T13:52:21 Z vjudge1 Klasika (COCI20_klasika) C++17
110 / 110
 1992 ms 428140 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 = 30;
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
11.0 / 11.0

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

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 7000 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 7004 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 2 ms 7136 KB Output is correct
13 Correct 4 ms 8028 KB Output is correct
14 Correct 5 ms 9196 KB Output is correct
15 Correct 6 ms 10568 KB Output is correct
16 Correct 7 ms 11612 KB Output is correct
17 Correct 4 ms 7772 KB Output is correct
18 Correct 5 ms 9048 KB Output is correct
19 Correct 6 ms 10332 KB Output is correct
20 Correct 6 ms 11356 KB Output is correct
21 Correct 4 ms 8028 KB Output is correct
22 Correct 5 ms 9052 KB Output is correct
23 Correct 6 ms 10328 KB Output is correct
24 Correct 7 ms 11356 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 125372 KB Output is correct
2 Correct 828 ms 228404 KB Output is correct
3 Correct 1165 ms 325100 KB Output is correct
4 Correct 1558 ms 423968 KB Output is correct
5 Correct 512 ms 122864 KB Output is correct
6 Correct 919 ms 224600 KB Output is correct
7 Correct 1343 ms 320772 KB Output is correct
8 Correct 1853 ms 417364 KB Output is correct
9 Correct 569 ms 122888 KB Output is correct
10 Correct 828 ms 224736 KB Output is correct
11 Correct 1215 ms 324264 KB Output is correct
12 Correct 1580 ms 419712 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 2 ms 7000 KB Output is correct
4 Correct 2 ms 7004 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 2 ms 6748 KB Output is correct
7 Correct 2 ms 7004 KB Output is correct
8 Correct 2 ms 7004 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 2 ms 6748 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 2 ms 7136 KB Output is correct
13 Correct 4 ms 8028 KB Output is correct
14 Correct 5 ms 9196 KB Output is correct
15 Correct 6 ms 10568 KB Output is correct
16 Correct 7 ms 11612 KB Output is correct
17 Correct 4 ms 7772 KB Output is correct
18 Correct 5 ms 9048 KB Output is correct
19 Correct 6 ms 10332 KB Output is correct
20 Correct 6 ms 11356 KB Output is correct
21 Correct 4 ms 8028 KB Output is correct
22 Correct 5 ms 9052 KB Output is correct
23 Correct 6 ms 10328 KB Output is correct
24 Correct 7 ms 11356 KB Output is correct
25 Correct 484 ms 125372 KB Output is correct
26 Correct 828 ms 228404 KB Output is correct
27 Correct 1165 ms 325100 KB Output is correct
28 Correct 1558 ms 423968 KB Output is correct
29 Correct 512 ms 122864 KB Output is correct
30 Correct 919 ms 224600 KB Output is correct
31 Correct 1343 ms 320772 KB Output is correct
32 Correct 1853 ms 417364 KB Output is correct
33 Correct 569 ms 122888 KB Output is correct
34 Correct 828 ms 224736 KB Output is correct
35 Correct 1215 ms 324264 KB Output is correct
36 Correct 1580 ms 419712 KB Output is correct
37 Correct 911 ms 129908 KB Output is correct
38 Correct 1392 ms 230616 KB Output is correct
39 Correct 1653 ms 332452 KB Output is correct
40 Correct 1742 ms 428140 KB Output is correct
41 Correct 1026 ms 126820 KB Output is correct
42 Correct 1506 ms 228688 KB Output is correct
43 Correct 1724 ms 325576 KB Output is correct
44 Correct 1992 ms 421188 KB Output is correct
45 Correct 1027 ms 125960 KB Output is correct
46 Correct 1535 ms 228876 KB Output is correct
47 Correct 1793 ms 324672 KB Output is correct
48 Correct 1801 ms 423532 KB Output is correct