結果

問題 No.3093 Safe Infection
ユーザー levyxx
提出日時 2025-04-06 17:25:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,776 bytes
コンパイル時間 4,479 ms
コンパイル使用メモリ 261,716 KB
実行使用メモリ 22,576 KB
最終ジャッジ日時 2025-04-13 19:22:08
合計ジャッジ時間 9,441 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 70 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, n) for (int i = (s); i < (int)(n); i++)
#include <atcoder/all>
using namespace atcoder;
using mint1 = modint1000000007;
using mint2 = modint998244353;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
ld pi=3.141592653589793;
const int inf=2e9;
const ll linf=2e18;
const ld eps=1e-14;
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl

ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};

struct edge{
    ll to;
    ll leng;
};

int main() {
    //////////////////
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //////////////////

    ll n,m,k;
    cin >> n >> m >> k;
    vector<ll> a(n),c(n);
    for(ll i=0; i<n; i++) {
        ll t;
        cin >> t;
        a[i]=t,c[i]=t;
    }
    dsu uf(n);
    vector<set<ll>> st(n);
    for(ll i=0; i<m; i++) {
        ll u,v;
        cin >> u >> v;
        u--,v--;
        uf.merge(u,v);
        st[u].insert(a[v]);
        st[v].insert(a[u]);
    }
    vector<vector<ll>> b(n);
    for(ll i=0; i<n; i++) {
        b[uf.leader(i)].push_back(a[i]);
    }
    sort(a.begin(), a.end());
    ll ma = a[n-1];
    for(ll i=0; i<n; i++) {
        sort(b[i].begin(), b[i].end());
        for(ll j=1; j<b[i].size(); j++) {
            if(b[i][j]-b[i][j-1] > k) {
                cout << "No" << endl;
                return 0;
            }

            if(j==b[i].size()-1) {
                if(b[i][j] != ma) {
                    cout << "No" << endl;
                    return 0;
                }
            }
        }
    }

    for(ll i=0; i<n; i++) {
        ll mi=*st[i].begin();
        if(mi>c[i] && mi-c[i]>k) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}
0