Submission #63552686

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<vector>
using namespace std;
#define ll long long
int fa[200010];
ll r[200010];
int find_anc(int u){
  if(fa[u]==u){
    r[u]=0;
    return u;
  }
  int tmp=fa[u];
  fa[u]=find_anc(fa[u]);
  r[u]^=r[tmp];
  return fa[u];
}
vector<int>g[200010];
ll a[200010];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<iostream>
#include<vector>
using namespace std;
#define ll long long

int fa[200010];
ll r[200010];

int find_anc(int u){
	if(fa[u]==u){
		r[u]=0;
		return u;
	}
	int tmp=fa[u];
	fa[u]=find_anc(fa[u]);
	r[u]^=r[tmp];
	return fa[u];
}

vector<int>g[200010];
ll a[200010];

int main(){
	iostream::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=0;i<m;i++){
		int u,v;	
		ll w;
		cin>>u>>v>>w;
		int fu=find_anc(u),fv=find_anc(v);
		if(fu==fv){
			// cout<<u<<" "<<v<<" "<<r[u]<<" "<<r[v]<<" "<<(r[u]^r[v])<<endl; 
			if((r[u]^r[v])!=w)cout<<-1,exit(0);
		}else{
			fa[fv]=fu;
			// u->fu = r[u]
			// v->fv = r[v]
			// u->v = w
			// fu->fv = fu->u->v->fv = r[u]^w^r[v]
			r[fv]=r[u]^r[v]^w;
		}
	}
	for(int i=1;i<=n;i++){
		find_anc(i);
		if(fa[i]!=i)g[fa[i]].push_back(i);
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		if(g[i].empty())continue;
		for(int j=31;j+1;j--){
			ll sum1=0,sum2=1ll<<j;
			for(auto id:g[i]){
				sum1+=(1ll<<j)&r[id];
			}
			for(auto id:g[i]){
				sum2+=(1ll<<j)&(r[id]^(1ll<<j));
			}
			if(sum1<sum2){
				for(auto id:g[i]){
					a[id]+=(1ll<<j)&r[id];
				}
			}else{
				for(auto id:g[i]){
					a[id]+=(1ll<<j)&(r[id]^(1ll<<j));
				}
				a[i]+=(1ll<<j);
			}
		}
	}
	for(int i=1;i<=n;i++)cout<<a[i]<<" ";
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:51:12: warning: unused variable ‘ans’ [-Wunused-variable]
   51 |         ll ans=0;
      |            ^~~

Judge Result