Submission #63512912

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <bitset>
#include <set>
#define ll long long
#define N 500010
using namespace std;
ll read(){
	char cc;
	while(1){cc=getchar();if((cc>='0'&&cc<='9')||cc=='-')break;}
	ll sum=0,flag=1;
	cc=='-'?flag=-1:sum=(cc^48);
	while(1){cc=getchar();if(!(cc>='0'&&cc<='9'))break;sum=(sum<<1)+(sum<<3)+(cc^48);}
	return sum*flag;
}
void write(ll x){
	if(!x)putchar('0');
	if(x<0){x=-x;putchar('-');}
	ll cc[25],cntt=0;
	while(x){cc[++cntt]=x%10;x/=10;}
	for(ll i=cntt;i>=1;i--)putchar(cc[i]+'0');
	putchar(' ');
	// putchar('\n');
}

vector <pair<ll,ll> >b[N];
ll n,m,a[N],t[32],flag=0,vis[N],s[N],shu,S,col[N],c[N],cnt=0;

void dfs(ll x){
	if(flag)return ;
	vis[x]=1;
	col[x]=cnt;
	for(ll i=0;i<30;i++)if((s[x]>>i)&1)t[i]++;
	shu++;
	for(pair<ll,ll> y:b[x]){
		if(flag)return ;
		ll v=y.first,w=y.second;
		if(vis[v]){
			if(w!=(s[x]^s[v])){flag=1;return ;}
		}
		else {
			s[v]=s[x]^w;
			dfs(v);
		}
	}
}	
int main(){
	n=read();m=read();
	for(ll u,v,w,i=1;i<=m;i++){
		u=read();v=read();w=read();
		b[u].push_back(make_pair(v,w));
		b[v].push_back(make_pair(u,w));
	}
	for(ll i=1;i<=n&&!flag;i++)if(!vis[i]){
		shu=0;cnt++;
		memset(t,0,sizeof(t));
		dfs(i);
		if(flag)break;
		S=0;
		for(ll j=0;j<30;j++)if(shu-t[j]<t[j])S|=(1<<j);
		c[cnt]=S;
	}
	if(flag){printf("-1\n");return 0;}
	for(ll i=1;i<=n;i++)write(s[i]^c[col[i]]);
	return 0;
}/*















*/

Submission Info

Judge Result