結果
問題 | No.3093 Safe Infection |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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; }