Submission #2522723

---

Source Code Expand

//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
#define pb push_back//also for STRING
typedef long long ll;//not necessarily//Be careful in topcoder.

struct unionfind{
	vector<int> par,rk;
	vector<ll> x,xold;

	unionfind(){}
	
	unionfind(const int n){
		par.resize(n);
		rk.resize(n);
		x.resize(n);
		xold.resize(n);
		for(int i=0;i<n;++i) par[i]=i;
		fill(rk.begin(),rk.end(),0);
		for(int i=0;i<n;++i) x[i]=((ll)i+1ll)*2000000000ll;
		for(int i=0;i<n;++i) xold[i]=((ll)i+1ll)*2000000000ll;
	}

	int find(int k){
//		printf("find(%d)\n",k);
		if(par[k]==k){
			return k;
		}else{
			if(abs(x[par[k]]-x[k])>1000000000ll){
				xold[k]=x[k];
				x[k]+=x[par[k]]-xold[par[k]];
			}
			par[k]=find(par[k]);
			return par[k]=find(par[k]);
		}
	}

	bool unite(int l,int r,ll d){
//		printf("unite(%d,%d,%lld)\n",l,r,d);
		int p=find(l),q=find(r);
		if(p==q){
			if(x[r]-x[l]!=d) return false;
			else return true;
		}
		//x[r]-x[l]==d x[q]-x[p]==d+(x[q]-x[r])-(x[p]-x[l])
		if(rk[p]<rk[q]){
			par[p]=q;
			xold[p]=x[p];
			x[p]=x[q]-d-(x[q]-x[r])+(x[p]-x[l]);
		}else{
			par[q]=p;
			xold[q]=x[q];
			x[q]=x[p]+d+(x[q]-x[r])-(x[p]-x[l]);
			if(rk[p]==rk[q]){
				++rk[p];
			}
		}
		return true;
	}

	bool same(int x,int y){
		return find(x)==find(y);
	}
};

int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	unionfind u(n);
	bool ans=true;
	while(m-- > 0){
		int l,r;
		ll d;
		scanf("%d %d %lld",&l,&r,&d);
		if(ans) ans=u.unite(--l,--r,d);
	}
	if(ans) printf("Yes\n");
	else printf("No\n");
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:68:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
./Main.cpp:74:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %lld",&l,&r,&d);
                               ^

Judge Result