結果

問題 No.3426 Mod K Graph Increments (Hard)
コンテスト
ユーザー shingo0909
提出日時 2026-01-11 14:04:48
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 249 ms / 2,000 ms
コード長 1,198 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,323 ms
コンパイル使用メモリ 343,276 KB
実行使用メモリ 16,768 KB
最終ジャッジ日時 2026-01-11 14:04:52
合計ジャッジ時間 4,787 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(){
    int t;
    cin >> t;
    while(t--){
        int n,m,k;
        cin >> n >> m >> k;
        vector<vector<int>>g(n);
        vector<ll>b(n);
        rep(i,m){
            int u,v;
            cin >> u >> v;
            u--;v--;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        rep(i,n)cin >> b[i];
        vector<int>d(n,-1);
        bool ok=true;
        function<void(int)> dfs=[&](int i){
            for(int j:g[i]){
                if(d[j]==-1){
                    d[j]=(d[i]^1);
                    dfs(j);
                }else{
                    if(d[i]==d[j])ok=false;
                }
            }
            return ;
        };
        d[0]=0;
        dfs(0);
        ll x=0;
        rep(i,n){
            if(d[i]==1)x-=b[i];
            else x+=b[i];
        }
        if(ok){
            cout << (abs(x)%k==0?"Yes":"No") << endl;
        }else{
            if(k%2)cout << "Yes" << endl;
            else {
                cout << (abs(x)%2==0?"Yes":"No") << endl;
            }
        }
    }

    return 0;
}
0