結果
問題 | No.3093 Safe Infection |
ユーザー |
|
提出日時 | 2025-04-06 16:09:48 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 119 ms / 2,000 ms |
コード長 | 2,692 bytes |
コンパイル時間 | 3,643 ms |
コンパイル使用メモリ | 288,688 KB |
実行使用メモリ | 11,904 KB |
最終ジャッジ日時 | 2025-04-06 16:09:59 |
合計ジャッジ時間 | 9,652 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 70 |
ソースコード
#include <bits/stdc++.h> // #include <atcoder/all> using namespace std; // using namespace atcoder; #define rep(i, a, n) for(int i = a; i < n; i++) #define rrep(i, a, n) for(int i = a; i >= n; i--) #define inr(l, x, r) (l <= x && x < r) #define ll long long #define ld long double // using mint = modint1000000007; // using mint = modint998244353; constexpr int IINF = 1001001001; constexpr ll INF = 1e18; template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;} template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;} vector<int> a; class UnionFind { vector<ll> parent, maxi, mini; inline ll root(ll n){ return (parent[n] < 0? n:parent[n] = root(parent[n])); } public: UnionFind(ll n_ = 1): parent(n_, -1), maxi(n_), mini(n_){ rep(i, 0, n_){ maxi[i] = a[i]; } iota(mini.begin(), mini.end(), 0); } inline bool same(ll x, ll y){ return root(x) == root(y); } inline void unite(ll x, ll y){ ll rx = root(x); ll ry = root(y); if(rx == ry) return; if(parent[rx] > parent[ry]) swap(rx, ry); parent[rx] += parent[ry]; parent[ry] = rx; maxi[rx] = std::max(maxi[rx],maxi[ry]); mini[rx] = std::min(mini[rx],mini[ry]); } inline ll min(ll x){ return mini[root(x)]; } inline ll max(int x){ return maxi[root(x)]; } inline ll size(ll x){ return (-parent[root(x)]); } inline ll operator[](ll x){ return root(x); } inline void print(){ rep(i, 0, (ll)parent.size()) cout << root(i) << " "; cout << endl; } void clear(){ rep(i, 0, (ll)parent.size()){ parent[i] = -1; } iota(maxi.begin(), maxi.end(), 0); iota(mini.begin(), mini.end(), 0); } }; int main(){ int n, m, k; cin >> n >> m >> k; a.resize(n); rep(i, 0, n) cin >> a[i]; vector<vector<int>> g(n); rep(i, 0, m){ int u, v; cin >> u >> v; u--, v--; g[v].push_back(u); g[u].push_back(v); } vector<int> ind(n); iota(ind.begin(), ind.end(), 0); sort(ind.begin(), ind.end(), [&](int i, int j){ return a[i] < a[j]; }); UnionFind uf(n); vector<bool> seen(n); for(auto u: ind){ for(auto v: g[u]){ if(!seen[v]) continue; // cout << u << ' ' << uf.max(u) << ' ' << v << ' ' << uf.max(v) << endl; if(uf.max(u)-uf.max(v) > k){ cout << "No" << endl; return 0; } uf.unite(u, v); } seen[u] = true; } cout << "Yes" << endl; return 0; }