結果
問題 | No.3093 Safe Infection |
ユーザー |
|
提出日時 | 2025-04-08 01:07:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 60 ms / 2,000 ms |
コード長 | 1,754 bytes |
コンパイル時間 | 2,797 ms |
コンパイル使用メモリ | 210,012 KB |
実行使用メモリ | 11,008 KB |
最終ジャッジ日時 | 2025-04-08 01:07:47 |
合計ジャッジ時間 | 7,132 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 70 |
ソースコード
#include <bits/stdc++.h> using namespace std; class UnionFind{ private: vector<int> par,siz; vector<int> dat; public: UnionFind(int N,const vector<int> &A){ par.resize(N,-1); siz.resize(N,1); dat = A; } int root(int x){ //連結成分の代表頂点を返す. if(par.at(x) == -1) return x; else return par.at(x) = root(par.at(x)); } int unite(int u, int v){ //u,vを連結する 連結してた->false,した->trueを返す. u = root(u),v = root(v); if(u == v) return 0; if(siz.at(u) < siz.at(v)) swap(u,v); //Union by size. par.at(v) = u; siz.at(u) += siz.at(v); int diff = abs(dat.at(u)-dat.at(v)); dat.at(u) = max(dat.at(u),dat.at(v)); return diff; } bool issame(int u, int v){ //同じ連結成分ならtrue. if(root(u) == root(v)) return true; else return false; } int size(int pos){return siz.at(root(pos));} //posの連結成分の大きさを返す. }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N,M,K; cin >> N >> M >> K; vector<int> A(N); for(auto &a : A) cin >> a; vector<vector<int>> Graph(N); for(int i=0; i<M; i++){ int u,v; cin >> u >> v; u--; v--; Graph.at(u).push_back(v); Graph.at(v).push_back(u); } UnionFind Z(N,A); vector<pair<int,int>> B(N); for(int i=0; i<N; i++) B.at(i) = {A.at(i),i}; sort(B.begin(),B.end()); for(auto [a,pos] : B){ for(auto to : Graph.at(pos)){ if(a < A.at(to)) continue; int diff = Z.unite(pos,to); if(diff > K){cout << "No\n"; return 0;} } } cout << "Yes\n"; }