Train

Solution Approach

This is a two-player graph game with a reachability/B\"uchi objective (visit good nodes infinitely often).

Algorithm: Use backward induction / attractor computation.

1. Find all nodes from which no charging station is reachable. Player B wins from these nodes (the train eventually gets stuck without charging). Mark these as losing for A.

2. From the remaining graph, find the attractor of the losing set:

   • A node controlled by B is losing if any successor leads to a losing node.

   • A node controlled by A is losing if all successors lead to losing nodes.

   • Repeat: in the remaining graph, check if all nodes can reach a charging station. Remove those that cannot and recompute.

   • The process converges. Remaining nodes are winning for A. enumerate

     More precisely, this is solved by computing the winning region for the B\"uchi game:

     1. Compute $W_B$ (losing for A): initially empty.

     2. Repeat:

        1. Remove nodes in $W_B$ from the graph.

        2. Find nodes that cannot reach any charging station in the remaining graph. Add them to $W_B$.

        3. Compute the attractor of $W_B$ (for player B): nodes where B can force reaching $W_B$.

        4. Until $W_B$ stabilizes. The complement is $W_A$.

        C++ Solution

        #include <bits/stdc++.h>
        using namespace std;
        
        vector<int> who_wins(int n, int m, vector<int> &owner,
                             vector<int> &charge,
                             vector<vector<int>> &adj,
                             vector<vector<int>> &radj) {
            // owner[i]: 0 = A, 1 = B
            // charge[i]: 1 = charging station, 0 = not
            // adj[i]: outgoing edges from i
            // radj[i]: incoming edges to i
        
            vector<bool> removed(n, false);
            vector<int> out_deg(n);
            for (int i = 0; i < n; i++) out_deg[i] = adj[i].size();
        
            bool changed = true;
            while (changed) {
                changed = false;
        
                // Step 1: Find nodes that cannot reach any charging station
                // BFS backward from all charging stations (not removed)
                vector<bool> canReach(n, false);
                queue<int> q;
                for (int i = 0; i < n; i++) {
                    if (!removed[i] && charge[i]) {
                        canReach[i] = true;
                        q.push(i);
                    }
                }
                while (!q.empty()) {
                    int u = q.front(); q.pop();
                    for (int v : radj[u]) {
                        if (!removed[v] && !canReach[v]) {
                            canReach[v] = true;
                            q.push(v);
                        }
                    }
                }
        
                // Nodes that can't reach charging: mark as losing (remove)
                queue<int> losing;
                for (int i = 0; i < n; i++) {
                    if (!removed[i] && !canReach[i]) {
                        removed[i] = true;
                        losing.push(i);
                        changed = true;
                    }
                }
        
                // Step 2: Compute attractor of losing nodes (for player B)
                // Recompute out_deg for remaining nodes (minus removed successors)
                // A node controlled by B: if any successor is removed -> it's losing
                // A node controlled by A: if all successors are removed -> it's losing
        
                // Reset out_deg to count non-removed successors
                vector<int> cur_deg(n, 0);
                for (int i = 0; i < n; i++) {
                    if (removed[i]) continue;
                    for (int j : adj[i]) {
                        if (!removed[j]) cur_deg[i]++;
                    }
                }
        
                while (!losing.empty()) {
                    int u = losing.front(); losing.pop();
                    for (int v : radj[u]) {
                        if (removed[v]) continue;
                        cur_deg[v]--;
                        if (owner[v] == 1) {
                            // B controls v: B can choose to go to removed node -> v is losing
                            removed[v] = true;
                            losing.push(v);
                            changed = true;
                        } else {
                            // A controls v: losing only if all successors removed
                            if (cur_deg[v] == 0) {
                                removed[v] = true;
                                losing.push(v);
                                changed = true;
                            }
                        }
                    }
                }
            }
        
            vector<int> result(n);
            for (int i = 0; i < n; i++) {
                result[i] = removed[i] ? 0 : 1; // 1 = A wins, 0 = B wins
            }
            return result;
        }
        
        int main() {
            int n, m;
            scanf("%d %d", &n, &m);
            vector<int> owner(n), charge(n);
            for (int i = 0; i < n; i++) scanf("%d", &owner[i]);
            for (int i = 0; i < n; i++) scanf("%d", &charge[i]);
            vector<vector<int>> adj(n), radj(n);
            for (int i = 0; i < m; i++) {
                int u, v;
                scanf("%d %d", &u, &v);
                adj[u].push_back(v);
                radj[v].push_back(u);
            }
            vector<int> res = who_wins(n, m, owner, charge, adj, radj);
            for (int i = 0; i < n; i++) printf("%d\n", res[i]);
            return 0;
        }

        Complexity Analysis

        • Time: $O(n \cdot (n + m))$ in the worst case, since the outer loop can iterate $O(n)$ times and each iteration does $O(n + m)$ work. In practice, each node is removed at most once, giving amortized $O(n + m)$ total for the attractor computation, but the reachability BFS might repeat.

        • With careful implementation (only re-check reachability for affected regions), the total time is $O(n \cdot (n + m))$.

        • Space: $O(n + m)$.