結果
問題 | No.3093 Safe Infection |
ユーザー |
|
提出日時 | 2025-04-06 17:30:51 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 108 ms / 2,000 ms |
コード長 | 2,631 bytes |
コンパイル時間 | 1,385 ms |
コンパイル使用メモリ | 117,236 KB |
実行使用メモリ | 18,968 KB |
最終ジャッジ日時 | 2025-04-06 17:30:57 |
合計ジャッジ時間 | 6,410 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 70 |
ソースコード
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; class UnionFind { public: vector<int> par, rank, siz; vector<priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>>> weight; int cnt; UnionFind(int n, vector<vector<pair<int, int>>> &w) { par.assign(n, -1); rank.assign(n, 0); siz.assign(n, 1); weight.resize(n); cnt = n; for (int i = 0; i < n; ++i) { for (auto &p : w[i]) { weight[i].push(p); } } } int root(int x) { if (par[x] == -1) return x; return par[x] = root(par[x]); } bool unite(int x, int y) { int px = root(x); int py = root(y); if (px == py) return false; if (rank[px] < rank[py]) swap(px, py); par[py] = px; if (rank[px] == rank[py]) rank[px]++; siz[px] += siz[py]; cnt--; // priority_queue の統合 if (weight[px].size() < weight[py].size()) { swap(weight[px], weight[py]); } while (!weight[py].empty()) { auto g = weight[py].top(); weight[py].pop(); if (root(g.second) == px) continue; weight[px].push(g); } return true; } int count() { return cnt; } int size(int x) { return siz[root(x)]; } priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> &getweight(int x) { return weight[root(x)]; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, M, K; cin >> N >> M >> K; vector<int> A(N); for (int i = 0; i < N; ++i) cin >> A[i]; vector<vector<pair<int, int>>> G(N); for (int i = 0; i < M; ++i) { int u, v; cin >> u >> v; --u; --v; G[u].emplace_back(A[v], v); G[v].emplace_back(A[u], u); } UnionFind UF(N, G); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> dp; for (int i = 0; i < N; ++i) { dp.emplace(A[i], i); } while (UF.count() > 1) { if (dp.empty()) break; auto [a, i] = dp.top(); dp.pop(); int ri = UF.root(i); auto &heap = UF.getweight(i); while (!heap.empty()) { auto [s, j] = heap.top(); heap.pop(); int rj = UF.root(j); if (ri == rj) continue; if (s - a > K) { cout << "No\n"; return 0; } UF.unite(i, j); break; } } cout << "Yes\n"; return 0; }