結果

問題 No.3426 Mod K Graph Increments (Hard)
コンテスト
ユーザー hirakuuuu
提出日時 2026-01-11 16:18:59
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 5,971 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,189 ms
コンパイル使用メモリ 358,448 KB
実行使用メモリ 16,780 KB
最終ジャッジ日時 2026-01-11 16:19:06
合計ジャッジ時間 5,751 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define rrep(i, a, n) for(int i = a; i >= n; i--)
#define inr(l, x, r) (l <= x && x < r)
#define ll long long
#define ld long double

// using mint = modint1000000007;
// using mint = modint998244353;
constexpr int IINF = 1001001001;
constexpr ll INF = 1e18;

template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

template <class E, class V, E (*merge)(E, E), E (*e)(), E (*put_edge)(V, int), V (*put_vertex)(E, int)>
class RerootingDP
{
    int n, root, inner_edge_id;
    vector<E> outs;
    struct edge {
        int to, idx, xdi;
    };
    vector<edge> es;
    vector<int> start;

    int outs_start(int v){
        int res = start[v]-v;
        if(root < v) res++;
        return res;
    }

    void es_build(){
        vector<edge> nes(2*n-2);
        vector<int> nstart(n+2, 0);
        for(int i = 0; i < 2*n-2; i++){
            nstart[start[i]+2]++;
        }
        for(int i = 0; i < n; i++){
            nstart[i+1] += nstart[i];
        }
        for(int i = 0; i < 2*n-2; i++){
            nes[nstart[start[i]+1]++] = es[i];
        }
        swap(es, nes);
        swap(start, nstart);
    }
    
public:
    RerootingDP(int n_ = 0) : n(n_), inner_edge_id(0) {
        es.resize(2*n-2);
        start.resize(2*n-2);
        if(n == 1) es_build();
    }

    void add_edge(int u, int v, int idx, int xdi){ // u→v, v→uの有向辺をそれぞれ追加
        start[inner_edge_id] = u;
        es[inner_edge_id] = {v, idx, xdi};
        inner_edge_id++;
        start[inner_edge_id] = v;
        es[inner_edge_id] = {u, xdi, idx};
        inner_edge_id++;
        if(inner_edge_id == 2*n-2){
            es_build();
        }
    }

    vector<V> build(int root_ = 0){
        root = root_;
        vector<V> subdp(n); subdp[0] = put_vertex(e(), 0);
        outs.resize(n);
        vector<int> geta(n+1, 0);
        for(int i = 0; i < n; i++){
            geta[i+1] = start[i+1]-start[i]-1;
        }
        geta[root+1]++;
        for(int i = 0; i < n; i++){
            geta[i+1] += geta[i];
        }

        auto dfs = [&](auto sfs, int v, int f)-> void {
            E val = e();
            for(int i = start[v]; i < start[v+1]; i++){
                if(es[i].to == f){
                    swap(es[start[v+1]-1], es[i]);
                }
                if(es[i].to == f) continue;
                sfs(sfs, es[i].to, v);
                E nval = put_edge(subdp[es[i].to], es[i].idx);
                outs[geta[v]++] = nval;
                val = merge(val, nval);
            }
            subdp[v] = put_vertex(val, v);
        };
        dfs(dfs, root, -1);
        return subdp;
    }

    vector<V> reroot(){
        vector<E> reverse_edge(n);
        reverse_edge[root] = e();
        vector<V> answers(n);
        auto dfs = [&](auto sfs, int v) -> void {
            int le = outs_start(v);
            int ri = outs_start(v+1);
            int siz = ri-le;
            vector<E> rui(siz+1);
            rui[siz] = e();
            for(int i = siz-1; i >= 0; i--){
                rui[i] = merge(outs[le+i], rui[i+1]);
            }
            answers[v] = put_vertex(merge(rui[0], reverse_edge[v]), v);
            E lui = e();
            for(int i = 0; i < siz; i++){
                V rdp = put_vertex(merge(merge(lui, rui[i+1]), reverse_edge[v]), v);
                reverse_edge[es[start[v]+i].to] = put_edge(rdp, es[start[v]+i].xdi);
                lui = merge(lui, outs[le+i]);
                sfs(sfs, es[start[v]+i].to);
            }
        };
        dfs(dfs, root);
        return answers;
    }
};

vector<ll> b;

using E = ll;
using V = ll;
ll k;
vector<int> v1, v2;
E merge(E x, E y){
    return (x+y)%k;
}
E e(){
    return E(0);
}
E put_edge(V v, int i){
    if(i%2 == 0) return (b[v2[i/2]]-v+k)%k;
    return (b[v1[i/2]]-v+k)%k;
}
V put_vertex(E e, int v){
    return e;
}



int main(){
    int t; cin >> t;
    while(t--){
        int n, m; cin >> n >> m;
        cin >> k;
        if(m == n-1){
            RerootingDP<E, V, merge, e, put_edge, put_vertex> g(n);
            v1.resize(m), v2.resize(m);
            rep(i, 0, m){
                cin >> v1[i] >> v2[i]; v1[i]--, v2[i]--;
                g.add_edge(v1[i], v2[i], 2*i, 2*i+1);
            }

            b.resize(n);
            rep(i, 0, n) cin >> b[i];
            
            g.build();
            bool ok = false;
            vector<V> root = g.reroot();
            rep(i, 0, n){
                if(root[i] == b[i]) ok = true;
            }
            if(ok) cout << "Yes" << endl;
            else cout << "No" << endl;
        }else{
            vector<vector<int>> g(n);
            rep(i, 0, m){
                int u, v; cin >> u >> v; u--, v--;
                g[u].push_back(v);
                g[v].push_back(u);
            }
            ll sum = 0;
            b.resize(n);
            rep(i, 0, n){
                cin >> b[i];
                sum += b[i];
            }
            if(k%2 == 0 && sum%2 == 1){
                cout << "No" << endl;
                continue;
            }

            vector<int> col(n, -1);
            queue<int> que;
            que.push(0);
            col[0] = 0;
            bool bi = true;
            while(!que.empty()){
                int q = que.front(); que.pop();
                for(auto nq: g[q]){
                    if(col[nq] != -1){
                        if(col[q] != col[nq]) continue;
                        bi = false;
                    }else{
                        col[nq] = 1-col[q];
                        que.push(nq);
                    }
                }
            }
            if(!bi){
                cout << "Yes" << endl;
            }else{
                cout << "No" << endl;
            }
        }
    }
    
    
    return 0;
}
0