結果
| 問題 | No.3426 Mod K Graph Increments (Hard) |
| コンテスト | |
| ユーザー |
 hirakuuuu
|
| 提出日時 | 2026-01-11 16:25:57 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 258 ms / 2,000 ms |
| コード長 | 6,164 bytes |
| 記録 | |
| コンパイル時間 | 4,136 ms |
| コンパイル使用メモリ | 358,340 KB |
| 実行使用メモリ | 16,696 KB |
| 最終ジャッジ日時 | 2026-01-11 16:26:03 |
| 合計ジャッジ時間 | 5,795 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge6 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 10 |
ソースコード
#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{
vector<ll> tot(2);
rep(i, 0, n){
tot[col[i]] += b[i];
}
if(tot[0]%k == tot[1]%k) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
}
return 0;
}