QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#860336#1168. Find the XORcoderjmcWA 0ms7332kbC++141.0kb2025-01-18 12:39:452025-01-18 12:39:49

Judging History

This is the latest submission verdict.

  • [2025-01-18 12:39:49]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 7332kb
  • [2025-01-18 12:39:45]
  • Submitted

answer

#include<iostream>
#include<vector>
#define int long long
#define endl "\n"
using namespace std;
const int N=1e5+5;
struct st{
	int v,w;
};
vector<st> edge[N];
int a[N],p[N];
bool vis[N];
void insert(int x){
	for(int i=30;i>=0;i--){
		if(!(x>>i))continue;
		if(!p[i]){
			p[i]=x;
			break;
		}
		x^=p[i];
	}
}
void dfs(int u,int sum){
	a[u]=sum;vis[u]=true;
	for(int i=0;i<edge[u].size();i++){
		int v=edge[u][i].v,w=edge[u][i].w;
		if(!vis[v])dfs(v,sum^w);
		else insert(sum^a[v]^w);
	}
}
int query(int x){
	for(int i=30;i>=0;i--)x=max(x,x^p[i]);
	return x;
}
signed main(){
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(false);
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		edge[u].push_back({v,w});
		edge[v].push_back({u,w});
	}
	dfs(1,0);
	int maxx=query(0);
	for(int i=1;i<=n;i++)a[i]^=a[i-1];
	while(q--){
		int l,r;
		cin>>l>>r;
		int x=r-l,ans=0;
		if(x&1)ans^=query(a[r]^a[l-1]);
		if((x*(x+1)/2)&1)ans^=maxx;
		cout<<ans<<endl;
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 7332kb

input:

8 10 7
1 2 662784558
3 2 195868257
3 4 294212653
4 5 299265014
6 5 72652580
6 7 29303370
7 8 183954825
2 1 752722885
5 3 197591314
8 4 877461873
4 8
5 7
6 7
2 3
7 8
3 4
2 7

output:

0
713437792
24900968
3442856
24040256
290292495
274579732

result:

wrong answer 3rd numbers differ - expected: '738051848', found: '24900968'