結果

問題 No.1640 簡単な色塗り
ユーザー 沙耶花
提出日時 2021-08-06 22:38:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 214 ms / 2,000 ms
コード長 2,191 bytes
コンパイル時間 4,626 ms
コンパイル使用メモリ 263,296 KB
最終ジャッジ日時 2025-01-23 15:57:26
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 53
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:85:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   85 |                 scanf("%d %d",&A[i],&B[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf 1000000000000000

vector<int> get(vector<int> a,vector<int> b){
	int n = a.size();
	vector<vector<int>> E(n);
	rep(i,n){
		E[a[i]].push_back(i);
		E[b[i]].push_back(i);
	}
	vector<int> ret(n,-1);
	vector<int> cnt(n);
	queue<int> Q;
	rep(i,n){
		cnt[i] = E[i].size();
		if(cnt[i]==1)Q.push(i);
	}
	
	while(Q.size()>0){
		int u = Q.front();
		Q.pop();
		
		rep(i,E[u].size()){
			int v = a[E[u][i]] ^ b[E[u][i]] ^ u;
			if(ret[E[u][i]]!=-1)continue;
			ret[E[u][i]] = u;
			cnt[v]--;
			if(cnt[v]==1){
				Q.push(v);
			}
			break;
		}
	}
	{
		vector<vector<int>> e(n);
		rep(i,n){
			if(ret[i]==-1){
				e[a[i]].push_back(i);
				e[b[i]].push_back(i);
			}
		}
		swap(E,e);
	}
	
	rep(i,n){
		if(E[i].size()==0)continue;
		int cur = i;
		while(true){
			bool f = false;
			rep(j,E[cur].size()){
				int to = a[E[cur][j]] ^ b[E[cur][j]] ^ cur;
				if(ret[E[cur][j]]==-1){
					cnt[to] = -1;
					ret[E[cur][j]] = to;
					cur = to;
					f = true;
					break;
				}
			}
			if(!f)break;
		}
		
		break;
	}
	
	return ret;
	
}

int main(){
	
	int N;
	cin>>N;
	
	vector<int> A(N),B(N);
	
	dsu D(N);
	rep(i,N){
		scanf("%d %d",&A[i],&B[i]);
		A[i]--;B[i]--;
		
		D.merge(A[i],B[i]);
	}
	
	vector<int> p(N);
	auto g = D.groups();
	rep(i,g.size()){
		rep(j,g[i].size()){
			p[g[i][j]] = i;
		}
	}
	
	vector<vector<int>> inds(g.size());
	
	rep(i,N){
		inds[p[A[i]]].push_back(i);
	}
	
	rep(i,g.size()){
		if(inds[i].size() != g[i].size()){
			cout<<"No"<<endl;
			return 0;
		}
	}
	
	cout<<"Yes"<<endl;
	vector<int> ans(N);
	rep(i,g.size()){
		sort(g[i].begin(),g[i].end());
		
		vector<int> aa(g[i].size()),bb(g[i].size());
		
		rep(j,inds[i].size()){
			int k = inds[i][j];
			aa[j] = distance(g[i].begin(),lower_bound(g[i].begin(),g[i].end(),A[k]));
			bb[j] = distance(g[i].begin(),lower_bound(g[i].begin(),g[i].end(),B[k]));
		}
		vector<int> ret = get(aa,bb);
		rep(j,ret.size()){
			int k = inds[i][j];
			ans[k] = g[i][ret[j]];
		}
		
	}
	
	rep(i,N){
		cout<<ans[i]+1<<endl;
	}
	
	return 0;
}
0