Submission #2545529

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int val[maxn*20],hd[maxn],n,m;
int to[maxn*20],ne[maxn*20],num,S;
int XS[maxn],now,ci[20],d[maxn],C[233];
inline void add(int x,int y,int z){ to[++num]=y,ne[num]=hd[x],hd[x]=num,val[num]=z;}
inline void build(){
	for(int i=1;i<ci[15];i++)
	    for(int j=1;j<=15;j++) if(ci[j-1]&i){
	    	now=i^ci[j-1],add(now,i,1);
	    	for(int k=1;k<=15;k++) if(ci[k-1]&now) add(now^ci[k-1]^ci[(j^k)-1],i,1+((now&ci[(j^k)-1])?1:0));
		}
}
inline void spfa(){
	queue<int> q; bool v[maxn];
	memset(d,0x3f,sizeof(d));
	memset(v,0,sizeof(v));
	d[0]=0,q.push(0),v[0]=1;
	int x;
	while(!q.empty()){
		x=q.front(),q.pop();
		for(int i=hd[x];i;i=ne[i]) if(d[x]+val[i]<d[to[i]]){
			d[to[i]]=d[x]+val[i];
			if(!v[to[i]]) v[to[i]]=1,q.push(to[i]);
		}
		v[x]=0;
	}
}
inline void init(){
	ci[0]=1;
	for(int i=1;i<=15;i++) ci[i]=ci[i-1]<<1;
	build();
	spfa();
}
inline void solve(){
	int uu,vv,ww,ans=1<<30;
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d%d",&uu,&vv,&ww);
		uu++,vv++,XS[uu]^=ww,XS[vv]^=ww;
	}
	for(int i=1;i<=n;i++) C[XS[i]]++;
	for(int i=1;i<=n;i++){
		C[XS[i]]--;
		S=0,now=0;
		for(int j=1;j<=15;j++){
			now+=C[j]>>1;
			S|=(C[j]&1)*ci[j-1];
		}
		now+=d[S];
		ans=min(ans,now);		
		C[XS[i]]++;
	}	
	printf("%d\n",ans);
}
int main(){
	init();
	solve();
}

Submission Info

Compile Error

./Main.cpp: In function ‘void solve()’:
./Main.cpp:38:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:40:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&uu,&vv,&ww);
                              ^

Judge Result