結果
問題 | No.3093 Safe Infection |
ユーザー |
![]() |
提出日時 | 2025-04-06 16:06:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 64 ms / 2,000 ms |
コード長 | 3,084 bytes |
コンパイル時間 | 4,130 ms |
コンパイル使用メモリ | 260,244 KB |
実行使用メモリ | 12,204 KB |
最終ジャッジ日時 | 2025-04-06 16:06:28 |
合計ジャッジ時間 | 7,803 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 70 |
ソースコード
#include <bits/stdc++.h> using namespace std; //* #include <atcoder/all> using namespace atcoder; using mint = modint998244353; // using mint = modint1000000007; //*/ using ll = long long; using i128 = __int128_t; using pll = pair<ll, ll>; using tlll = tuple<ll, ll, ll>; using ld = long double; const int INF = 1000100100; const ll INFF = 1000100100100100100LL; const int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0}; #define overload4(_1, _2, _3, _4, name, ...) name #define rep1(i, n) for (ll i = 0; i < ll(n); i++) #define rep2(i, l, r) for (ll i = ll(l); i < ll(r); i++) #define rep3(i, l, r, d) for (ll i = ll(l); (d) > 0 ? i < ll(r) : i > ll(r); i += d) #define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define per(i, n) for (int i = (n) - 1; i >= 0; --i) #define yesno(f) cout << (f ? "Yes" : "No") << endl; #define YESNO(f) cout << (f ? "YES" : "NO") << endl; #define all(a) (a).begin(), (a).end() #define popc(x) __builtin_popcountll(ll(x)) template <typename S, typename T> ostream &operator<<(ostream &os, const pair<S, T> &p) { return os << p.first << ' ' << p.second; } template <typename T> void printvec(const vector<T> &v) { int n = v.size(); rep(i, n) cout << v[i] << (i == n - 1 ? "" : " "); cout << '\n'; } template <typename T> void printvect(const vector<T> &v) { for (auto &vi : v) cout << vi << '\n'; } template <typename T> void printvec2(const vector<vector<T>> &v) { for (auto &vi : v) printvec(vi); } template <typename S, typename T> bool chmax(S &x, const T &y) { return (x < y) ? (x = y, true) : false; } template <typename S, typename T> bool chmin(S &x, const T &y) { return (x > y) ? (x = y, true) : false; } #ifdef LOCAL // https://zenn.dev/sassan/articles/19db660e4da0a4 #include "cpp-dump-main/dump.hpp" #define dump(...) cpp_dump(__VA_ARGS__) CPP_DUMP_DEFINE_DANGEROUS_EXPORT_OBJECT(val()); #else #define dump(...) #endif struct io_setup { io_setup() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout << fixed << setprecision(15); } } io_setup; void solve() { int n, m, k; cin >> n >> m >> k; vector<int> a(n); rep(i, n) cin >> a[i]; vector<vector<int>> g(n); rep(i, m) { int u, v; cin >> u >> v; u--, v--; g[u].push_back(v); g[v].push_back(u); } vector<pll> v; rep(i, n) v.emplace_back(a[i], i); sort(all(v)); vector<bool> vis(n, false); priority_queue<pll, vector<pll>, greater<pll>> pq; pq.emplace(v[0].first, v[0].second); int now = v[0].first; vis[v[0].second] = true; while (!pq.empty()) { auto [pos, p] = pq.top(); pq.pop(); if (pos - now > k) { cout << "No" << endl; return; } now = pos; for (auto e : g[p]) { if (!vis[e]) { pq.emplace(a[e], e); vis[e] = true; } } } cout << "Yes" << endl; } int main() { int t; // cin >> t; t = 1; while (t--) { solve(); } }