/**
* Super cute problem~ Here's how I solved it.
*
* [S1-2] Simple case / brute-force
* [S3] A has control over all stations. For each charging station c, we wanna know
* the set of starting nodes which can trap the train in a cycle with station c.
* First, we find all nodes that can reach c. Then, we find whether there's a
* directed cycle containing c. If one is found, all those nodes can reach c
* and be trapped by some cycle. (Simply neglect a suffix of cycle if there're
* overlapping nodes)
* [S4] I forgot what I did. Anyway it wasn't a correct solution for [S4].
* [S5] I consider a simpler case: the unique charging station only has an out-going
* self-loop. Here, whenever we enter that station, it's guaranteed that the
* train goes on forever (~ we don't have to worry about entering the station
* at some point but A can force the train out of it).
* Call a node good if we return 1 for it. All of A's nodes that directly link
* to the charger are definitely good. Wait, the charger is good too! And, all
* of B's nodes that only directly link to the charger or other good nodes are
* good too.
* In general, we can do a BFS on the reversed graph. If a A node can lead to a
* good node, it's good; if a B node can ONLY lead to good nodes, it's good. In
* practice, we can decrease the out deg of a B node by 1 each time,
* effectively removing an edge, just as we did in Kahn’s algorithm for
* topological sort.
*
* It took me a while before I can rigorously prove that the BFS in [S5] is indeed
* correct. Define S to be the set of nodes which aren't good after the completion of
* BFS. We know by definition our rule of BFS that
* (1) For a in S (a is from A), a only leads to nodes in S;
* (2) For b in S (b is from B), b leads to at least one node in S.
* This means that for each b in S, B can randomly direct the train to any node in S.
* A cannot do nothing with S, so S is in some sense "closed". Whenever the train
* enters S, it cannot be trapped in a cycle with the charging station.
*
* No idea how to solve the full problem.... The greatest issue is that our strategy
* shouldn't be to "force the train into a particular station". Well, the idea is
* that the train can be trapped in a cycle with a charger does not imply that it
* can always be trapped in one with a particular charger...
*
* (After a while...)
* [Lemma] Consider an alternative game, in which nodes visited before allows the
* owner to re-select their out-going edges.
* This version of the game has the same winning/losing situations.
* Indeed, [Lemma] is just a clearer way of phrasing the following:
* If ans[u] = 1, "they" can reach a charger. From that charger, "they" can
* reach another charger, which can then reach the next charger, and so on.
* In other words, if ans[u] = 1, "they" can always reach a charger v with
* ans[v] = 1 by traversing one or more edges. The formulation is recursive.
*
* I then realize that this recursion can be transformed into an "iterative" one. By
* [Lemma], it suffices to find the successful charging stations and see whether the
* non-charging stations can reach those. Let S_1 denote the set of chargers s.t.
* starting from any s in S_1, "they" can traverse through >=1 edges to reach another
* charging station. Similar, define S_2 to be the set of chargers starting from
* which "they" can reach chargers in S_1, i.e. from these stations, "they" can go to
* one charger, and subsequently go to another one. Therefore, S_{i+1} can be found
* from S_i with BFS.
*
* The key is to notice that S_{n+1} are the only charging stations from which A can
* win. Indeed, if ans[u] = 1, we can start from u and reach chargers for an inf num
* of times (by [Lemma]), so it has to be in S_{n+1}. On the other hand, if A can
* reach (n+1) (not necessarily distinct) chargers from u no matter how B plays, then
* at some point the train would be trapped in a cycle with a charger (original
* problem).
*
* Time Complexity: O(nm) (Full Solution)
* Implementation 1 (BFS)
*/
#include <bits/stdc++.h>
#include "train.h"
typedef std::vector<int> vec;
vec who_wins(vec owner, vec charge, vec u, vec v) {
int n = owner.size(), m = u.size();
vec out_deg(n, 0);
std::vector<vec> rev_graph(n);
for (int e = 0; e < m; e++) {
rev_graph[v[e]].push_back(u[e]);
out_deg[u[e]]++;
/**
* Super cute problem~ Here's how I solved it.
*
* [S1-2] Simple case / brute-force
* [S3] A has control over all stations. For each charging station c, we wanna know
* the set of starting nodes which can trap the train in a cycle with station c.
* First, we find all nodes that can reach c. Then, we find whether there's a
* directed cycle containing c. If one is found, all those nodes can reach c
* and be trapped by some cycle. (Simply neglect a suffix of cycle if there're
* overlapping nodes)
* [S4] I forgot what I did. Anyway it wasn't a correct solution for [S4].
* [S5] I consider a simpler case: the unique charging station only has an out-going
* self-loop. Here, whenever we enter that station, it's guaranteed that the
* train goes on forever (~ we don't have to worry about entering the station
* at some point but A can force the train out of it).
* Call a node good if we return 1 for it. All of A's nodes that directly link
* to the charger are definitely good. Wait, the charger is good too! And, all
* of B's nodes that only directly link to the charger or other good nodes are
* good too.
* In general, we can do a BFS on the reversed graph. If a A node can lead to a
* good node, it's good; if a B node can ONLY lead to good nodes, it's good. In
* practice, we can decrease the out deg of a B node by 1 each time,
* effectively removing an edge, just as we did in Kahn’s algorithm for
* topological sort.
*
* It took me a while before I can rigorously prove that the BFS in [S5] is indeed
* correct. Define S to be the set of nodes which aren't good after the completion of
* BFS. We know by definition our rule of BFS that
* (1) For a in S (a is from A), a only leads to nodes in S;
* (2) For b in S (b is from B), b leads to at least one node in S.
* This means that for each b in S, B can randomly direct the train to any node in S.
* A cannot do nothing with S, so S is in some sense "closed". Whenever the train
* enters S, it cannot be trapped in a cycle with the charging station.
*
* No idea how to solve the full problem.... The greatest issue is that our strategy
* shouldn't be to "force the train into a particular station". Well, the idea is
* that the train can be trapped in a cycle with a charger does not imply that it
* can always be trapped in one with a particular charger...
*
* (After a while...)
* [Lemma] Consider an alternative game, in which nodes visited before allows the
* owner to re-select their out-going edges.
* This version of the game has the same winning/losing situations.
* Indeed, [Lemma] is just a clearer way of phrasing the following:
* If ans[u] = 1, "they" can reach a charger. From that charger, "they" can
* reach another charger, which can then reach the next charger, and so on.
* In other words, if ans[u] = 1, "they" can always reach a charger v with
* ans[v] = 1 by traversing one or more edges. The formulation is recursive.
*
* I then realize that this recursion can be transformed into an "iterative" one. By
* [Lemma], it suffices to find the successful charging stations and see whether the
* non-charging stations can reach those. Let S_1 denote the set of chargers s.t.
* starting from any s in S_1, "they" can traverse through >=1 edges to reach another
* charging station. Similar, define S_2 to be the set of chargers starting from
* which "they" can reach chargers in S_1, i.e. from these stations, "they" can go to
* one charger, and subsequently go to another one. Therefore, S_{i+1} can be found
* from S_i with BFS.
*
* The key is to notice that S_{n+1} are the only charging stations from which A can
* win. Indeed, if ans[u] = 1, we can start from u and reach chargers for an inf num
* of times (by [Lemma]), so it has to be in S_{n+1}. On the other hand, if A can
* reach (n+1) (not necessarily distinct) chargers from u no matter how B plays, then
* at some point the train would be trapped in a cycle with a charger (original
* problem).
*
* Time Complexity: O(nm) (Full Solution)
* Implementation 1 (BFS)
*/
#include <bits/stdc++.h>
#include "train.h"
typedef std::vector<int> vec;
vec who_wins(vec owner, vec charge, vec u, vec v) {
int n = owner.size(), m = u.size();
vec out_deg(n, 0);
std::vector<vec> rev_graph(n);
for (int e = 0; e < m; e++) {
rev_graph[v[e]].push_back(u[e]);
out_deg[u[e]]++;
}
vec win = charge; // S_i
for (int r = 1; r <= n + 1; r++) {
std::queue<int> bfs_queue;
std::vector<bool> visited(n, false); // has been in queue?
for (int k = 0; k < n; k++) {
if (win[k]) {
bfs_queue.push(k);
visited[k] = true;
assert(charge[k]);
}
}
vec out_copy = out_deg;
vec win_next(n, 0); // S_{i+1}, essentially a boolean array
while (!bfs_queue.empty()) {
int t = bfs_queue.front();
bfs_queue.pop();
for (int prev : rev_graph[t]) {
if (win_next[prev])
continue;
out_copy[prev]--;
if (owner[prev] == 1 || (owner[prev] == 0 && out_copy[prev] == 0)) {
win_next[prev] = 1;
if (!visited[prev]) {
bfs_queue.push(prev);
visited[prev] = true;
}
}
}
}
// Include non-charging stations only in the last round, so that win[] will
// directly be the answer to the problem. Note that S_i only contains
// chargers, but for impl we allow S_{n+1} to contain non-charging ones.
if (r < n + 1) {
for (int k = 0; k < n; k++)
win_next[k] &= charge[k]; // S_{i+1} should only contain chargers
}
std::swap(win, win_next);
}
return win;
}
Compilation message
train.cpp: In function 'vec who_wins(vec, vec, vec, vec)':
train.cpp:158:51: error: a function-definition is not allowed here before '{' token
158 | vec who_wins(vec owner, vec charge, vec u, vec v) {
| ^
train.cpp:207:1: error: expected '}' at end of input
207 | }
| ^
train.cpp:80:33: note: to match this '{'
80 | for (int e = 0; e < m; e++) {
| ^
train.cpp:207:1: error: expected '}' at end of input
207 | }
| ^
train.cpp:76:51: note: to match this '{'
76 | vec who_wins(vec owner, vec charge, vec u, vec v) {
| ^
train.cpp:207:1: warning: no return statement in function returning non-void [-Wreturn-type]
207 | }
| ^
