結果

問題 No.3425 Mod K Graph Increments (Easy)
コンテスト
ユーザー NaH54i
提出日時 2026-01-11 14:50:38
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 190 ms / 2,000 ms
コード長 1,684 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,778 ms
コンパイル使用メモリ 349,872 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2026-01-11 14:50:43
合計ジャッジ時間 5,495 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
using ll = long long;
using ld = long double;
//using mint = modint998244353;
int main(){
    ll T;
    cin >> T;
    while(T--){
        ll n,m,k;
        cin >> n >> m >> k;

        vector<vector<ll>> pass(n,vector<ll>(0));
        vector<pair<ll,ll>> way(0);
        //unordered_map<ll,ll> cost;
        ll u,v;

        for(ll i = 0; i < m; i++){
            cin >> u >> v;
            u--;
            v--;
            pass[u].push_back(v);
            pass[v].push_back(u);
        }

        vector<ll> b(n,0);
        
        for(ll i = 0; i < n; i++){
            cin >> b[i];
        }

        bool ans = 1;
        queue<ll> bfs;
        vector<bool> come(n,0);
        vector<ll> num(n,0);
        

        for(ll i = 0; i < n; i++){
            num[i] = pass[i].size();
            if(num[i] == 1){
                bfs.push(i);
            }
        }


        while(!bfs.empty()){
            ll x = bfs.front();
            bfs.pop();
            if(come[x])continue;
            come[x] = 1;
            //if(num[x] > 1)break;

            for(ll i : pass[x]){
                if(come[i])continue;
                num[i]--;
                num[x]--;

                b[i] += k;
                b[i] -= b[x];
                b[i] %= k;
                b[x] = 0;

                if(num[i] == 1)bfs.push({i});
            }
        }

        for(ll i = 0; i < n; i++){
            if(b[i] != 0){
                ans = 0;
                break;
            }
        }

        if(ans)cout << "Yes" << '\n';
        else cout << "No" << '\n';
    }



    return 0;
}
0