Submission #256807

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
256807	2020-08-03T08:46:58 Z	MrRobot_28	Klasika (COCI20_klasika)	C++17	33 / 110	1041 ms	524292 KB

klasika

#include<bits/stdc++.h>
 
using namespace std;
int n = 1;
vector <vector <pair <int, int> > > g;
vector <int> h, tin, tout;
int timer = 0;
void dfs(int v, int p = -1)
{
	tin[v] = timer++;
	for(int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i].first;
		int w = g[v][i].second;
		if(to != p)
		{
			h[to] = h[v] ^ w;
			dfs(to, v);
		}
	}
	tout[v] = timer - 1;
}
struct node{
	node* left;
	node* right;
	node(){
	left = NULL;
	right = NULL;};
};
vector <node*> tree;
void go_down(node* &w, int i, int val)
{
	if(i < 0)
	{
		return;
	}
	if(val & (1LL << i))
	{
		if(!w -> right)
		{
			w -> right = new node();
		}
		go_down(w -> right, i - 1, val);
	}
	else
	{
		if(!w -> left)
		{
			w -> left = new node();
		}
		go_down(w -> left, i - 1, val);
	}
}
void update(int v, int l, int r, int ind, int val)
{
	go_down(tree[v], 30, val);
	if(l == r)
	{
		return;
	}
	if(ind <= (r + l) / 2)
	{
		update(v * 2, l, (r + l) / 2, ind, val);
	}
	else
	{
		update(v * 2 + 1, (r + l) / 2 + 1, r, ind, val);
	}
}
int ans(int v, int l, int r, int al, int ar, int val)
{
	if(l >= al && r <= ar)
	{
		if(!tree[v] -> left && !tree[v] -> right)
		{
			return val;
		}
		int val1 = (1LL << 31) - val - 1;
		node* w = tree[v];
		int valans = 0;
		for(int i = 30; i >= 0; i--)
		{
			if(val1 & (1LL << i))
			{
				if(!w -> right)
				{
					w = w -> left;
				}
				else
				{
					w = w -> right;
					valans += (1LL << i);
				}
			}
			else
			{
				if(!w -> left)
				{
					w = w -> right;
					valans += (1LL << i);
				}
				else
				{
					w = w -> left;
				}
			}
		}
		return valans;
	}
	else if(l <= ar && r >= al)
	{
		int t1 = ans(v * 2, l, (r + l) / 2, al, ar, val);
		int t2 = ans(v * 2 + 1, (r + l) / 2 + 1, r, al, ar, val);
		if((t1 ^ val) > (t2 ^ val))
		{
			return t1;
		}
		return t2;
	}
	else
	{
		return val;
	}
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int q;
	cin >> q;
	vector <string> type(q);
	vector <pair <int, int> > mass(q);
	for(int i = 0; i < q; i++){
		cin >> type[i];
		cin >> mass[i].first >> mass[i].second;
		if(type[i] == "Add"){
			n++;
		}
	}
	g.resize(n);
	h.resize(n);
	tin.resize(n);
	tout.resize(n);
	int cnt = 1;
	for(int i = 0; i < q; i++)
	{
		if(type[i] == "Add")
		{
			mass[i].first--;
			g[mass[i].first].push_back({cnt, mass[i].second});
			cnt++;
		}
	}
	dfs(0);
	tree.resize(4 * n);
	for(int i = 0; i < 4 * n; i++){
		tree[i] = new node();
	}
	cnt = 1;
	update(1, 0, n - 1, tin[0], 0);
	for(int i = 0; i < q; i++)
	{
		if(type[i] == "Add")
		{
			update(1, 0, n - 1, tin[cnt], h[cnt]);
			cnt++;
		}
		else
		{
			mass[i].first--;
			mass[i].second--;
			int val = h[mass[i].first];
			int val1 = ans(1, 0, n - 1, tin[mass[i].second], tout[mass[i].second], val);
			cout << (val ^ val1) << "\n";
		}
	}
	return 0;
}

Compilation message

klasika.cpp: In function 'void dfs(int, int)':
klasika.cpp:11:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[v].size(); i++)
                 ~~^~~~~~~~~~~~~

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	640 KB	Output is correct
2	Correct	1 ms	896 KB	Output is correct
3	Correct	2 ms	1152 KB	Output is correct
4	Correct	2 ms	1536 KB	Output is correct
5	Correct	1 ms	512 KB	Output is correct
6	Correct	1 ms	768 KB	Output is correct
7	Correct	2 ms	1152 KB	Output is correct
8	Correct	2 ms	1536 KB	Output is correct
9	Correct	1 ms	640 KB	Output is correct
10	Correct	2 ms	1024 KB	Output is correct
11	Correct	2 ms	1280 KB	Output is correct
12	Correct	2 ms	1536 KB	Output is correct

Subtask #2

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	640 KB	Output is correct
2	Correct	1 ms	896 KB	Output is correct
3	Correct	2 ms	1152 KB	Output is correct
4	Correct	2 ms	1536 KB	Output is correct
5	Correct	1 ms	512 KB	Output is correct
6	Correct	1 ms	768 KB	Output is correct
7	Correct	2 ms	1152 KB	Output is correct
8	Correct	2 ms	1536 KB	Output is correct
9	Correct	1 ms	640 KB	Output is correct
10	Correct	2 ms	1024 KB	Output is correct
11	Correct	2 ms	1280 KB	Output is correct
12	Correct	2 ms	1536 KB	Output is correct
13	Correct	9 ms	4096 KB	Output is correct
14	Correct	14 ms	7936 KB	Output is correct
15	Correct	19 ms	12160 KB	Output is correct
16	Correct	24 ms	16120 KB	Output is correct
17	Correct	8 ms	3712 KB	Output is correct
18	Correct	12 ms	7680 KB	Output is correct
19	Correct	19 ms	11904 KB	Output is correct
20	Correct	24 ms	15872 KB	Output is correct
21	Correct	8 ms	3840 KB	Output is correct
22	Correct	13 ms	7808 KB	Output is correct
23	Correct	18 ms	11896 KB	Output is correct
24	Correct	22 ms	15864 KB	Output is correct

Subtask #3

0 / 33.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1041 ms	500496 KB	Output is correct
2	Runtime error	896 ms	524292 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
3	Halted	0 ms	0 KB	-

Subtask #4

0 / 44.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	640 KB	Output is correct
2	Correct	1 ms	896 KB	Output is correct
3	Correct	2 ms	1152 KB	Output is correct
4	Correct	2 ms	1536 KB	Output is correct
5	Correct	1 ms	512 KB	Output is correct
6	Correct	1 ms	768 KB	Output is correct
7	Correct	2 ms	1152 KB	Output is correct
8	Correct	2 ms	1536 KB	Output is correct
9	Correct	1 ms	640 KB	Output is correct
10	Correct	2 ms	1024 KB	Output is correct
11	Correct	2 ms	1280 KB	Output is correct
12	Correct	2 ms	1536 KB	Output is correct
13	Correct	9 ms	4096 KB	Output is correct
14	Correct	14 ms	7936 KB	Output is correct
15	Correct	19 ms	12160 KB	Output is correct
16	Correct	24 ms	16120 KB	Output is correct
17	Correct	8 ms	3712 KB	Output is correct
18	Correct	12 ms	7680 KB	Output is correct
19	Correct	19 ms	11904 KB	Output is correct
20	Correct	24 ms	15872 KB	Output is correct
21	Correct	8 ms	3840 KB	Output is correct
22	Correct	13 ms	7808 KB	Output is correct
23	Correct	18 ms	11896 KB	Output is correct
24	Correct	22 ms	15864 KB	Output is correct
25	Correct	1041 ms	500496 KB	Output is correct
26	Runtime error	896 ms	524292 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
27	Halted	0 ms	0 KB	-