結果
問題 | No.3093 Safe Infection |
ユーザー |
![]() |
提出日時 | 2025-04-06 16:24:30 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 254 ms / 2,000 ms |
コード長 | 2,048 bytes |
コンパイル時間 | 3,718 ms |
コンパイル使用メモリ | 301,208 KB |
実行使用メモリ | 27,348 KB |
最終ジャッジ日時 | 2025-04-06 16:24:48 |
合計ジャッジ時間 | 12,782 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 70 |
ソースコード
#include<bits/stdc++.h> #define ALL(x) (x).begin(),(x).end() #define LB(v,x) (int)(lower_bound(ALL(v),x)-(v).begin()) #define UQ(v) sort(ALL(v)),(v).erase(unique(ALL(v)),(v).end()) #define IO ios::sync_with_stdio(false),cin.tie(nullptr); #define chmax(a,b)(a)=(a)<(b)?(b):(a) #define chmin(a,b)(a)=(a)<(b)?(a):(b) using namespace std; using ll=long long; const int INF=1e9+10; const ll INFL=4e18; struct DSU{ DSU()=default; DSU(int n){ par.resize(n); iota(par.begin(),par.end(),0); sz.assign(n,1); forest_count=n; } int find(int x){ if(par[x]==x)return x; return par[x]=find(par[x]); } bool merge(int x,int y){ x=find(x),y=find(y); if(x==y)return false; if(sz[x]<sz[y])swap(x,y); par[y]=x; sz[x]+=sz[y]; forest_count--; return true; } int size(int x){return sz[find(x)];} bool same(int x,int y){return find(x)==find(y);} int count(){return forest_count;} vector<vector<int>>groups(){ int n=par.size(); vector<vector<int>>ret(n); for(int i=0;i<n;i++)ret[find(i)].push_back(i); ret.erase(remove_if(ret.begin(),ret.end(),[&](const vector<int>&v){return v.empty();}),ret.end()); return ret; } private: vector<int>par,sz; int forest_count; }; /* 操作をする→頂点を縮約できる 最終的に1つの頂点にできるか? */ int main(){ ll N,M,K;cin>>N>>M>>K; vector<tuple<ll,ll,ll>>A(N); for(int i=0;i<N;i++)cin>>get<0>(A[i]),get<2>(A[i])=i; sort(ALL(A)); vector<int>inv(N); for(int i=0;i<N;i++)get<1>(A[i])=i,inv[get<2>(A[i])]=i; vector<set<tuple<ll,ll,ll>>>G(N); for(int i=0;i<M;i++){ int u,v;cin>>u>>v,u--,v--; G[u].insert(A[inv[v]]); G[v].insert(A[inv[u]]); } vector<bool>seen(N,false); DSU dsu(N); for(auto a:A){ auto[v,n,i]=a; if(G[i].count(a))G[i].erase(a); auto itr=G[i].lower_bound({v,n+1,-1}); if(itr==G[i].end())continue; auto[v2,n2,i2]=*itr; if(abs(v2-v)>K)continue; dsu.merge(i,i2); if(ssize(G[i])>ssize(G[i2]))G[i].swap(G[i2]); for(auto p:G[i])G[i2].insert(p); } puts(dsu.count()==1?"Yes":"No"); }