結果

問題 No.3426 Mod K Graph Increments (Hard)
コンテスト
ユーザー まみめ
提出日時 2025-11-22 18:56:39
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,997 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,560 ms
コンパイル使用メモリ 347,876 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2026-01-11 13:00:30
合計ジャッジ時間 6,278 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other RE * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    long long K;
    if(!(cin >> N >> M >> K)) return 0;
    vector<vector<int>> g(N+1);
    for(int i=0;i<M;i++){
        int u,v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<long long> B(N+1);
    for(int i=1;i<=N;i++) cin >> B[i];

    vector<int> color(N+1, -1);
    vector<char> vis(N+1, 0);
    const long long Kll = K;

    for(int s=1;s<=N;s++){
        if(vis[s]) continue;
        // BFS
        queue<int> q;
        q.push(s);
        vis[s] = 1;
        color[s] = 0;
        bool is_bip = true;
        ll sum0 = 0, sum1 = 0;
        ll sumAll = 0;
        vector<int> comp;
        while(!q.empty()){
            int v = q.front(); q.pop();
            comp.push_back(v);
            if(color[v]==0) sum0 = (sum0 + B[v]) ;
            else sum1 = (sum1 + B[v]) ;
            sumAll = (sumAll + B[v]);
            for(int to: g[v]){
                if(!vis[to]){
                    vis[to] = 1;
                    color[to] = color[v]^1;
                    q.push(to);
                }else{
                    if(color[to] == color[v]) is_bip = false;
                }
            }
        }
        // apply conditions
        if(is_bip){
            // need sum0 % K == sum1 % K
            long long a = sum0 % Kll;
            long long b = sum1 % Kll;
            if( ( (a - b) % Kll + Kll) % Kll != 0 ){
                cout << "No\n";
                return 0;
            }
        }else{
            // non-bipartite: need sumAll % gcd(2,K) == 0
            if(Kll % 2 == 0){
                // check parity of sumAll
                if( (sumAll % 2 + 2) % 2 != 0 ){
                    cout << "No\n";
                    return 0;
                }
            }else{
                // K odd -> always OK
            }
        }
    }

    cout << "Yes\n";
    return 0;
}
0