結果
問題 | No.3093 Safe Infection |
ユーザー |
![]() |
提出日時 | 2025-04-06 16:05:58 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 52 ms / 2,000 ms |
コード長 | 1,820 bytes |
コンパイル時間 | 3,931 ms |
コンパイル使用メモリ | 282,436 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-04-06 16:06:06 |
合計ジャッジ時間 | 6,848 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 70 |
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename Monoid> struct merge_tree { using S = typename Monoid::S; merge_tree(int n) : p(n, -1), d(n, Monoid::e()) {} merge_tree(const vector<S> &v) : p(v.size(), -1), d(v) {} void set(int u, const S &x) { d[u] = x; } int leader(int u) const { return p[u] < 0 ? u : leader(p[u]); } bool same(int u, int v) const { return leader(u) == leader(v); } int size(int u) const { return -p[leader(u)]; } S get(int u) const { return d[leader(u)]; } void merge(int u, int v) { u = leader(u); v = leader(v); if (u == v) return; if (size(u) < size(v)) swap(u, v); p[u] += p[v]; p[v] = u; d[u] = Monoid::op(d[u], d[v]); d[v] = Monoid::e(); } private: vector<int> p; vector<S> d; }; template <typename T, T E = -numeric_limits<T>::max()> struct max_monoid { using S = T; static S op(const S &a, const S &b) { return max(a, b); } static S e() { return E; } }; 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<int> u(M), v(M); for (int i = 0; i < M; i++) cin >> u[i] >> v[i], u[i]--, v[i]--; vector<int> ord(M); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&](int i, int j) { return max(A[u[i]], A[v[i]]) < max(A[u[j]], A[v[j]]); }); merge_tree<max_monoid<int>> uf(N); for (int i = 0; i < N; i++) { uf.set(i, A[i]); } for (int i : ord) { int a = uf.get(u[i]), b = uf.get(v[i]); if (abs(a - b) > K) { cout << "No\n"; return 0; } uf.merge(u[i], v[i]); } cout << "Yes\n"; }