oj.uz

답안 #1017970

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1017970 2024-07-09T12:07:27 Z vjudge1 Klasika (COCI20_klasika) C++17
66 / 110
 4123 ms 491084 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) v.begin(), v.end()

const int M = 2e5 + 2, thres = 2500;

vector<int> nei[M],ver[M*31];
int nxt[M*31][2],val[M],st[M],en[M],sz,t,parr[M];
stack<int> stk;

void dfs(int u)
{
	st[u]=t++;
	for (int i:nei[u])
		dfs(i);
	en[u]=t++;
	stk.push(u);
}

void add(int vl,int tm)
{
	int cur=0;
	for (int i=30;i>=0;i--)
	{
		int x=0;
		if ((1<<i)&vl)
			x=1;
		if (!nxt[cur][x])
			nxt[cur][x]=++sz;
		cur=nxt[cur][x];
		ver[cur].push_back(tm);
	}
}

int get(int vl,int s,int e)
{
	int cur=0,ans=0;
	for (int i=30;i>=0;i--)
	{
		int x=1;
		if ((1<<i)&vl)
			x=0;
		if (!nxt[cur][x])
			x=1-x;
		else if(lower_bound(all(ver[nxt[cur][x]]),s)==lower_bound(all(ver[nxt[cur][x]]),e))
			x=1-x;
		else
			ans+=(1LL<<i);
		cur=nxt[cur][x];
	}
	return ans;
}

void dfs1(int u,int vl,int &ans)
{
	ans=max(ans,val[u]^vl);
	for (int i:nei[u])
		dfs1(i,vl,ans);
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	int q;
	cin>>q;
	int nodes=2;
	vector<int> pen;
	while (q--)
	{
		string s;
		cin>>s;
		if (s=="Add")
		{
			int x,y;
			cin>>x>>y;
			val[nodes]=val[x]^y;
			pen.push_back(nodes);
			if (x<pen[0])
				parr[nodes]=x;
			else
				parr[nodes]=parr[x];
			nei[x].push_back(nodes++);
		}
		else
		{
			int a,b;
			cin>>a>>b;
			int ans=0;
			if (!pen.empty() && pen[0]<=b)
				dfs1(b,val[a],ans);
			else
			{
				if (nodes>thres)
					ans=get(val[a],st[b],en[b]);
				else
					ans=val[a];
				for (int i:pen)
				{
					if (parr[i]==b || (nodes>thres && st[parr[i]]>=st[b] && st[parr[i]]<en[b]))
						ans=max(ans,val[i]^val[a]);
				}
			}
			cout<<ans<<'\n';
		}
		if (pen.size()==thres)
		{
			for (int i=0;i<sz;i++)
				nxt[i][0]=nxt[i][1]=0,ver[i].clear();
			t=0;
			pen.clear();
			dfs(1);
			sz=0;
			while (!stk.empty())
				add(val[stk.top()],st[stk.top()]),stk.pop();
		}
	}
	
	return 0;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 151288 KB Output is correct
2 Correct 57 ms 151168 KB Output is correct
3 Correct 57 ms 151300 KB Output is correct
4 Correct 54 ms 151128 KB Output is correct
5 Correct 55 ms 151124 KB Output is correct
6 Correct 55 ms 151124 KB Output is correct
7 Correct 67 ms 151296 KB Output is correct
8 Correct 54 ms 151124 KB Output is correct
9 Correct 55 ms 151120 KB Output is correct
10 Correct 53 ms 151292 KB Output is correct
11 Correct 60 ms 151300 KB Output is correct
12 Correct 54 ms 151124 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 151288 KB Output is correct
2 Correct 57 ms 151168 KB Output is correct
3 Correct 57 ms 151300 KB Output is correct
4 Correct 54 ms 151128 KB Output is correct
5 Correct 55 ms 151124 KB Output is correct
6 Correct 55 ms 151124 KB Output is correct
7 Correct 67 ms 151296 KB Output is correct
8 Correct 54 ms 151124 KB Output is correct
9 Correct 55 ms 151120 KB Output is correct
10 Correct 53 ms 151292 KB Output is correct
11 Correct 60 ms 151300 KB Output is correct
12 Correct 54 ms 151124 KB Output is correct
13 Correct 55 ms 151124 KB Output is correct
14 Correct 61 ms 151360 KB Output is correct
15 Correct 61 ms 151380 KB Output is correct
16 Correct 55 ms 151376 KB Output is correct
17 Correct 57 ms 151120 KB Output is correct
18 Correct 56 ms 151128 KB Output is correct
19 Correct 52 ms 151344 KB Output is correct
20 Correct 55 ms 151380 KB Output is correct
21 Correct 56 ms 151376 KB Output is correct
22 Correct 56 ms 151124 KB Output is correct
23 Correct 53 ms 151124 KB Output is correct
24 Correct 69 ms 151124 KB Output is correct

Subtask #3
33.0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 623 ms 191156 KB Output is correct
2 Correct 971 ms 228156 KB Output is correct
3 Correct 1606 ms 260908 KB Output is correct
4 Correct 2769 ms 299456 KB Output is correct
5 Correct 660 ms 204772 KB Output is correct
6 Correct 1328 ms 289596 KB Output is correct
7 Correct 2362 ms 369724 KB Output is correct
8 Correct 4123 ms 491084 KB Output is correct
9 Correct 644 ms 191264 KB Output is correct
10 Correct 1040 ms 228648 KB Output is correct
11 Correct 1872 ms 260684 KB Output is correct
12 Correct 3094 ms 298912 KB Output is correct

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 151288 KB Output is correct
2 Correct 57 ms 151168 KB Output is correct
3 Correct 57 ms 151300 KB Output is correct
4 Correct 54 ms 151128 KB Output is correct
5 Correct 55 ms 151124 KB Output is correct
6 Correct 55 ms 151124 KB Output is correct
7 Correct 67 ms 151296 KB Output is correct
8 Correct 54 ms 151124 KB Output is correct
9 Correct 55 ms 151120 KB Output is correct
10 Correct 53 ms 151292 KB Output is correct
11 Correct 60 ms 151300 KB Output is correct
12 Correct 54 ms 151124 KB Output is correct
13 Correct 55 ms 151124 KB Output is correct
14 Correct 61 ms 151360 KB Output is correct
15 Correct 61 ms 151380 KB Output is correct
16 Correct 55 ms 151376 KB Output is correct
17 Correct 57 ms 151120 KB Output is correct
18 Correct 56 ms 151128 KB Output is correct
19 Correct 52 ms 151344 KB Output is correct
20 Correct 55 ms 151380 KB Output is correct
21 Correct 56 ms 151376 KB Output is correct
22 Correct 56 ms 151124 KB Output is correct
23 Correct 53 ms 151124 KB Output is correct
24 Correct 69 ms 151124 KB Output is correct
25 Correct 623 ms 191156 KB Output is correct
26 Correct 971 ms 228156 KB Output is correct
27 Correct 1606 ms 260908 KB Output is correct
28 Correct 2769 ms 299456 KB Output is correct
29 Correct 660 ms 204772 KB Output is correct
30 Correct 1328 ms 289596 KB Output is correct
31 Correct 2362 ms 369724 KB Output is correct
32 Correct 4123 ms 491084 KB Output is correct
33 Correct 644 ms 191264 KB Output is correct
34 Correct 1040 ms 228648 KB Output is correct
35 Correct 1872 ms 260684 KB Output is correct
36 Correct 3094 ms 298912 KB Output is correct
37 Correct 758 ms 194068 KB Output is correct
38 Correct 1088 ms 231228 KB Output is correct
39 Correct 1859 ms 265700 KB Output is correct
40 Correct 2790 ms 302492 KB Output is correct
41 Incorrect 916 ms 205884 KB Output isn't correct
42 Halted 0 ms 0 KB -