Submission #399530

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define rep(i,x,y) for(int i=(x); i<(y); ++i)
#define debug(x) #x << "=" << x
#ifdef DEBUG
	#define dump(x) cerr << debug(x) << " (LINE:" << __LINE__ << ")" << endl;
#else
	#define dump(x)
#endif

struct UnionFind{
	vector<int> par,rank;

	void Init(int n){
		par.assign(n,0);
		rank.assign(n,0);
		rep(i,0,n) par[i]=i;
	}

	int Find(int x){
		if(x==par[x]) return x;
		return par[x]=Find(par[x]);
	}

	void Unite(int x,int y){
		x=Find(x);
		y=Find(y);
		if(x==y) return;
		if(rank[x]<rank[y]){
			par[x]=y;
		}else{
			par[y]=x;
			if(rank[y]==rank[x]) ++rank[x];
		}
	}

	bool Same(int x,int y){
		return Find(x)==Find(y);
	}
};

typedef pair<int,int> pii;

void Solve(){
	int n,m,k;
	cin >> n >> m >> k;

	vector<int> a(m),b(m),c(m);
	vector<pii> ps;
	rep(i,0,m){
		//cin >> a[i] >> b[i] >> c[i];
		scanf("%d%d%d",&a[i],&b[i],&c[i]);
		--a[i]; --b[i];
		ps.push_back(make_pair(c[i],i));
	}
	sort(ps.rbegin(),ps.rend());

	vector<int> ans(m);
	vector<UnionFind> us(k);
	rep(i,0,k) us[i].Init(n);
	rep(i,0,m){
		int idx=ps[i].second;
		int ai=a[idx],bi=b[idx];
		int lb=0,ub=k;
		while(ub-lb>1){
			int mid=(lb+ub)/2;
			if(!us[mid].Same(ai,bi)) ub=mid;
			else lb=mid;
		}
		if(!us[lb].Same(ai,bi)) ub=lb;
		if(ub==k) continue;
		ans[idx]=ub+1;
		us[ub].Unite(ai,bi);
	}

	//rep(i,0,m) cout << ans[i] << endl;
	rep(i,0,m) printf("%d\n",ans[i]);
}

int main(){
	//cin.tie(0);
	//ios::sync_with_stdio(false);
	Solve();
}

Submission Info

Compile Error

./Main.cpp: In function ‘void Solve()’:
./Main.cpp:53:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&a[i],&b[i],&c[i]);
                                    ^

Judge Result