結果
| 問題 | No.3508 OR Mapping |
| コンテスト | |
| ユーザー |
 gojoxd
|
| 提出日時 | 2026-04-18 19:21:52 |
| 言語 | C (gcc 15.2.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,025 bytes |
| 記録 | |
| コンパイル時間 | 317 ms |
| コンパイル使用メモリ | 42,736 KB |
| 実行使用メモリ | 35,200 KB |
| 最終ジャッジ日時 | 2026-04-18 19:22:08 |
| 合計ジャッジ時間 | 8,775 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 54 WA * 11 |
ソースコード
/*
No.3508 OR Mapping
https://yukicoder.me/problems/13182
APPROACH:
We need to make every vertex's value = 2^K - 1 (all K bits set).
Each time we move to vertex j at time T (1-indexed), we OR in (T mod 2^K).
Key observations:
1. REACHABILITY: Every vertex must be reachable from vertex 1.
If any vertex is unreachable, we can never write to it → No.
2. VERTEX 1 MUST BE ON A CYCLE: Vertex 1's value only changes when we
move TO it. If vertex 1 has no incoming edges from reachable nodes
(i.e., not on any cycle), its value stays 0 → No (for K >= 1).
3. STRONGLY CONNECTED COMPONENTS (SCCs):
Within an SCC with cycle-gcd g (gcd of all cycle lengths),
if we enter the SCC at time T0, vertices in the SCC can be visited
at times T0, T0+g, T0+2g, T0+3g, ...
The OR of (T0 + i*g) mod 2^K over all i >= 0 equals 2^K - 1
iff g is ODD.
- If g is odd: gcd(g, 2^K) = 1, so multiples of g cover all residues
mod 2^K, and the OR of all visited time values = 2^K - 1. ✓
- If g is even: e.g. g=2, then every other bit position is unreachable
for certain vertices (those always visited at even times), so
we can never OR in all bits. ✗
4. TRIVIAL SCCs (single vertex, no self-loops allowed by constraints):
Visited at one specific time T per visit. Multiple visits are possible
by re-entering only if in the condensed DAG there are cycles, but the
condensed DAG is acyclic. So effectively visited at one time T.
However, we can adjust T arbitrarily by looping in any predecessor SCC
(which has odd gcd, so we can add any multiple of an odd number to T,
effectively reaching any residue mod 2^K).
For a trivial SCC to accumulate all bits: we need to visit it at
multiple different times... but it's a DAG node, visited at most once
per "session". Actually we can re-enter it if there's a path back
to it from itself — but that would make it non-trivial in Tarjan.
Wait: a trivial SCC means there's no cycle through it. So we visit it
at exactly one time T in any traversal. For it to get value 2^K - 1,
we need T mod 2^K = 2^K - 1. We can arrange this by looping in a
predecessor SCC with odd gcd to adjust T to any desired residue.
Since SCC(1) has odd gcd (condition 2), this is always achievable.
ALGORITHM:
1. Find all SCCs (Tarjan/Kosaraju).
2. Check all vertices reachable from vertex 1.
3. Check SCC(1) is non-trivial with odd cycle-gcd.
4. Check every non-trivial SCC reachable from vertex 1 has odd cycle-gcd.
Computing cycle-gcd of an SCC:
- BFS from any root within the SCC.
- For each edge (u -> v) in the SCC, contribute (dist[u] + 1 - dist[v]).
(Tree edges contribute 0; back/cross edges contribute cycle lengths.)
- g = gcd of all non-zero contributions.
Complexity: O(N + M) for SCC + O(N + M) for gcd computation = O(N + M).
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 500005
#define MAXM 500005
/* Forward graph */
int head[MAXN], nxt[MAXM], to_v[MAXM];
/* Reverse graph */
int rhead[MAXN], rnxt[MAXM], rto_v[MAXM];
int ecnt = 0;
int N, M;
long long K;
/* SCC */
int comp[MAXN]; /* SCC id of each vertex (1-indexed SCC ids) */
int scc_size[MAXN]; /* size of each SCC */
int scc_head[MAXN]; /* head of linked list of vertices in SCC */
int scc_nxt[MAXN]; /* linked list next pointer (0 = end) */
int scc_cnt = 0;
/* Kosaraju DFS order */
int order_arr[MAXN];
int ord_cnt = 0;
int vis[MAXN];
/* BFS */
int dist[MAXN];
int bfs_q[MAXN];
/* Iterative DFS stacks */
int stk[MAXN], stk_e[MAXN];
void add_edge(int u, int v) {
ecnt++;
to_v[ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt;
rto_v[ecnt] = u; rnxt[ecnt] = rhead[v]; rhead[v] = ecnt;
}
long long gcd(long long a, long long b) {
if (a < 0) a = -a;
if (b < 0) b = -b;
while (b) { long long t = b; b = a % b; a = t; }
return a;
}
int main() {
scanf("%d %d %lld", &N, &M, &K);
for (int i = 0; i < M; i++) {
int u, v;
scanf("%d %d", &u, &v);
add_edge(u, v);
}
/* -------- Kosaraju Step 1: DFS on original graph, record finish order -------- */
int stk_top = 0;
for (int i = 1; i <= N; i++) {
if (!vis[i]) {
stk[stk_top] = i;
stk_e[stk_top] = head[i];
stk_top++;
vis[i] = 1;
while (stk_top > 0) {
int u = stk[stk_top - 1];
int e = stk_e[stk_top - 1];
if (e) {
stk_e[stk_top - 1] = nxt[e];
int v = to_v[e];
if (!vis[v]) {
vis[v] = 1;
stk[stk_top] = v;
stk_e[stk_top] = head[v];
stk_top++;
}
} else {
order_arr[ord_cnt++] = u;
stk_top--;
}
}
}
}
/* -------- Kosaraju Step 2: DFS on reverse graph in reverse finish order -------- */
for (int i = ord_cnt - 1; i >= 0; i--) {
int start = order_arr[i];
if (!comp[start]) {
scc_cnt++;
int c = scc_cnt;
stk[0] = start;
stk_e[0] = rhead[start];
stk_top = 1;
comp[start] = c;
scc_size[c] = 1;
scc_nxt[start] = scc_head[c];
scc_head[c] = start;
while (stk_top > 0) {
int u = stk[stk_top - 1];
int e = stk_e[stk_top - 1];
if (e) {
stk_e[stk_top - 1] = rnxt[e];
int v = rto_v[e];
if (!comp[v]) {
comp[v] = c;
scc_size[c]++;
scc_nxt[v] = scc_head[c];
scc_head[c] = v;
stk[stk_top] = v;
stk_e[stk_top] = rhead[v];
stk_top++;
}
} else {
stk_top--;
}
}
}
}
/* -------- Check all vertices reachable from vertex 1 -------- */
/* BFS/DFS from vertex 1 on original graph */
memset(vis, 0, (N + 1) * sizeof(int));
stk[0] = 1; stk_top = 1; vis[1] = 1;
stk_e[0] = head[1];
int reach_cnt = 1;
while (stk_top > 0) {
int u = stk[stk_top - 1];
int e = stk_e[stk_top - 1];
if (e) {
stk_e[stk_top - 1] = nxt[e];
int v = to_v[e];
if (!vis[v]) {
vis[v] = 1;
reach_cnt++;
stk[stk_top] = v;
stk_e[stk_top] = head[v];
stk_top++;
}
} else {
stk_top--;
}
}
if (reach_cnt < N) {
printf("No\n");
return 0;
}
/* -------- Compute cycle-gcd for each SCC -------- */
/* dist[] is reused here: -1 = unvisited */
memset(dist, -1, (N + 1) * sizeof(int));
long long *scc_gcd_val = (long long *)calloc(scc_cnt + 1, sizeof(long long));
for (int c = 1; c <= scc_cnt; c++) {
if (scc_size[c] == 1) {
scc_gcd_val[c] = 0; /* trivial: no cycle */
continue;
}
/* BFS within SCC c */
int root = scc_head[c];
dist[root] = 0;
int qh = 0, qt = 0;
bfs_q[qt++] = root;
long long g = 0;
while (qh < qt) {
int u = bfs_q[qh++];
for (int e = head[u]; e; e = nxt[e]) {
int v = to_v[e];
if (comp[v] != c) continue; /* skip inter-SCC edges */
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
bfs_q[qt++] = v;
}
/* Cycle contribution: how much does this edge's back/cross
differ from a tree edge? */
long long cyc = (long long)dist[u] + 1 - dist[v];
if (cyc != 0) g = gcd(g, cyc);
}
}
/* Reset dist for vertices in this SCC */
for (int node = scc_head[c]; node; node = scc_nxt[node])
dist[node] = -1;
scc_gcd_val[c] = g;
}
/* -------- Check conditions -------- */
/* Condition: SCC containing vertex 1 must have odd cycle-gcd > 0 */
int c1 = comp[1];
if (scc_gcd_val[c1] == 0 || scc_gcd_val[c1] % 2 == 0) {
printf("No\n");
free(scc_gcd_val);
return 0;
}
/* Condition: every non-trivial SCC (reachable from 1, which is all of them
since we checked reachability) must have odd cycle-gcd */
for (int c = 1; c <= scc_cnt; c++) {
if (scc_size[c] > 1 && scc_gcd_val[c] % 2 == 0) {
printf("No\n");
free(scc_gcd_val);
return 0;
}
}
printf("Yes\n");
free(scc_gcd_val);
return 0;
}