結果

問題 No.3093 Safe Infection
コンテスト
ユーザー keisuke6
提出日時 2025-04-06 16:16:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 133 ms / 2,000 ms
コード長 1,295 bytes
コンパイル時間 2,778 ms
コンパイル使用メモリ 207,056 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-06 16:16:36
合計ジャッジ時間 8,004 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define int long long
int N,M,K;
int A[100100];
struct Unionfind{
private:
	int n;
	vector<int> par, siz;
public:
	Unionfind(int N){
		n = N;
		par.resize(n,-1);
		siz.resize(n,1);
	}
	int root(int a){
		if(par[a] == -1) return a;
		else return par[a] = root(par[a]);
	}
	bool issame(int a, int b){
		return (root(a) == root(b));
	}
	int size(int a){
		return siz[root(a)];
	}
	bool unite(int a, int b){
		a = root(a);
		b = root(b);
		if(a == b) return false;
		if(siz[a] > siz[b]) swap(a,b);
		siz[b] += siz[a];
		par[a] = b;
		A[b] = max(A[a],A[b]);
		return true;
	}
};
signed main(){
    cin>>N>>M>>K;
    for(int i=0;i<N;i++) cin>>A[i];
    vector<pair<int,int>> S(M);
    for(int i=0;i<M;i++){
    	int a,b;
    	cin>>a>>b;
    	a--;
    	b--;
    	if(A[a] < A[b]) swap(a,b);
    	S[i] = {a,b};
    }
    sort(S.begin(),S.end(),[&](const pair<int,int> a, pair<int,int> b){
    	if(A[a.first] != A[b.first]) return (A[a.first] < A[b.first]);
    	else return (A[a.second] < A[b.second]);
    });
    Unionfind uf(N);
    for(auto [a,b]:S){
    	a = uf.root(a);
    	b = uf.root(b);
    	if(uf.issame(a,b)) continue;
    	if(abs(A[a]-A[b]) > K){
    		cout<<"No"<<endl;
    		return 0;
    	}
    	uf.unite(a,b);
    }
    cout<<"Yes"<<endl;
}
0