結果
問題 | No.3093 Safe Infection |
ユーザー |
|
提出日時 | 2025-04-06 17:53:51 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 3,935 bytes |
コンパイル時間 | 4,433 ms |
コンパイル使用メモリ | 314,048 KB |
実行使用メモリ | 11,124 KB |
最終ジャッジ日時 | 2025-04-06 17:54:00 |
合計ジャッジ時間 | 8,610 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 70 |
ソースコード
#ifdef LOCAL #include <local.hpp> #else #pragma GCC optimize("O3") // #pragma target("arch=skylake-avx512") #include <bits/stdc++.h> #define debug(...) ((void)0) #endif // https://suisen-cp.github.io/cp-library-cpp/library/datastructure/union_find/union_find_component_sum.hpp.html #line 1 "library/datastructure/union_find/union_find_component_sum.hpp" #line 1 "library/datastructure/union_find/union_find.hpp" #include <algorithm> #include <vector> namespace suisen { struct UnionFind { UnionFind() = default; explicit UnionFind(int _n) : _n(_n), _dat(_n, -1) {} // Get the root of `x`. equivalent to `operator[](x)` int root(int x) { static std::vector<int> buf; while (_dat[x] >= 0) buf.push_back(x), x = _dat[x]; while (buf.size()) _dat[buf.back()] = x, buf.pop_back(); return x; } // Get the root of `x`. euivalent to `root(x)` int operator[](int x) { return root(x); } // Merge two vertices `x` and `y`. bool merge(int x, int y) { x = root(x), y = root(y); if (x == y) return false; if (_dat[x] > _dat[y]) std::swap(x, y); _dat[x] += _dat[y], _dat[y] = x; return true; } // Check if `x` and `y` belongs to the same connected component. bool same(int x, int y) { return root(x) == root(y); } // Get the size of connected componet to which `x` belongs. int size(int x) { return -_dat[root(x)]; } // Get all of connected components. std::vector<std::vector<int>> groups() { std::vector<std::vector<int>> res(_n); for (int i = 0; i < _n; ++i) res[root(i)].push_back(i); res.erase(std::remove_if(res.begin(), res.end(), [](const auto& g) { return g.empty(); }), res.end()); return res; } protected: int _n; std::vector<int> _dat; }; } // namespace suisen #line 5 "library/datastructure/union_find/union_find_component_sum.hpp" namespace suisen { template <typename T, void (*merge_data)(T&, T)> struct UnionFindComponentSum : UnionFind { UnionFindComponentSum() : UnionFindComponentSum(0) {} explicit UnionFindComponentSum(int n, const T& init_value = T{}) : UnionFindComponentSum(std::vector<T>(n, init_value)) {} explicit UnionFindComponentSum(const std::vector<T>& init_values) : UnionFind(init_values.size()), _sum(init_values) {} bool merge(int x, int y) { x = root(x), y = root(y); bool res = UnionFind::merge(x, y); if (res) { if (root(x) == y) std::swap(x, y); merge_data(_sum[x], std::move(_sum[y])); } return res; } const T& sum(int x) { return _sum[root(x)]; } private: std::vector<T> _sum; }; } // namespace suisen using namespace std; using ll = long long; using ld = long double; using T = ll; void merge(T& a, T b) { a = max(a, b); } void solve(int) { int N, M; ll K; cin >> N >> M >> K; vector<ll> A(N); for (auto&& x : A) { cin >> x; } vector<vector<int>> adj(N); for (int i = 0; i < M; i++) { int u, v; cin >> u >> v; u--, v--; adj[u].push_back(v); adj[v].push_back(u); } suisen::UnionFindComponentSum<T, merge> uf(A); vector<int> order(N); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [&](int i, int j) { return A[i] < A[j]; }); for (auto&& u : order) { for (auto&& v : adj[u]) { if (A[u] < uf.sum(v)) continue; if (A[u] - uf.sum(v) > K) { cout << "No" << endl; return; } uf.merge(u, v); } } cout << "Yes" << endl; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; for (int i = 1; i <= t; i++) { solve(i); } #ifdef LOCAL postprocess(); #endif }