結果

問題 No.1641 Tree Xor Query
ユーザー snrnsidysnrnsidy
提出日時 2021-08-10 17:12:58
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,971 bytes
コンパイル時間 2,237 ms
コンパイル使用メモリ 203,784 KB
実行使用メモリ 18,760 KB
最終ジャッジ日時 2024-09-22 18:37:59
合計ジャッジ時間 4,230 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,888 KB
testcase_01 WA -
testcase_02 AC 3 ms
6,016 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

vector <int> adj[100001];
long long int tree[300001];
long long int lazy[300001];
int L[100001];
int R[100001];
int arr[100001];

void dfs(int now,int prev,int &num)
{
	L[now] = ++num;
	for(auto next : adj[now])
	{
		if(prev==next)
		{
			continue;
		}
		dfs(next,now,num);
	}
	R[now] = num;
}

void propagate(int node,int start,int end)
{
	if(lazy[node]>0)
	{
		if((end-start+1)%2)
		{
			tree[node]^=lazy[node];
		}
		if(start!=end)
		{
			lazy[node*2]^=lazy[node];
			lazy[node*2+1]^=lazy[node];
		}
		lazy[node]=0;
	}
	return;
}

long long int update(int node,int start,int end,int left,int right,int value)
{
	propagate(node,start,end);

	if(left>end || right<start)
	{
		return tree[node];
	}

	if(left<=start && end<=right)
	{
		if((end-start+1)%2)
		{
			tree[node]^=value;
		}
		
		if(start!=end)
		{
			lazy[node*2]^=value;
			lazy[node*2+1]^=value;
		}
		
		//propagate(node,start,end);
		return tree[node];
	}

	int mid = (start+end)/2;

	tree[node] = update(node*2,start,mid,left,right,value)^update(node*2+1,mid+1,end,left,right,value);
	return tree[node];
}

long long int Xor(int node,int start,int end,int left,int right)
{
	propagate(node,start,end);

	if(left>end || right<start)
	{
		return 0;
	}

	if(left<=start && end<=right)
	{
		return tree[node];
	}

	int mid = (start+end)/2;

	return Xor(node*2,start,mid,left,right)^Xor(node*2+1,mid+1,end,left,right);
}


int main(void)
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n, m;
	
	cin >> n >> m;

	for(int i=1;i<=n;i++)
	{
		cin >> arr[i];
	}
	
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}


	int num = 0;
	dfs(1,0,num);

	for(int i=1;i<=n;i++)
	{
		update(1,1,n,L[i],L[i],arr[i]);
	}
	for(int i=0;i<m;i++)
	{
		int x,y,z;
		cin >> x;
		if(x==1)
		{
			cin >> y >> z;
			update(1,1,n,L[y],R[y],z);
		}
		else
		{
			cin >> y;
			cout << Xor(1,1,n,L[y],R[y]) << '\n';
		}
	}

	return 0;
}
0