/**
* 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
std::queue<int> bfs_queue;
for (int r = 1; r <= n + 1; r++) {
for (int k = 0; k < n; k++) {
if (win[k]) {
bfs_queue.push(k);
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;
bfs_queue.push(prev);
}
}
}
// 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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
662 ms |
932 KB |
3rd lines differ - on the 22nd token, expected: '0', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
296 KB |
3rd lines differ - on the 8th token, expected: '0', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
139 ms |
1316 KB |
Output is correct |
| 2 |
Correct |
168 ms |
1448 KB |
Output is correct |
| 3 |
Correct |
195 ms |
1456 KB |
Output is correct |
| 4 |
Correct |
958 ms |
1296 KB |
Output is correct |
| 5 |
Correct |
597 ms |
1296 KB |
Output is correct |
| 6 |
Correct |
112 ms |
1356 KB |
Output is correct |
| 7 |
Correct |
1155 ms |
1436 KB |
Output is correct |
| 8 |
Correct |
388 ms |
1284 KB |
Output is correct |
| 9 |
Correct |
93 ms |
1236 KB |
Output is correct |
| 10 |
Correct |
618 ms |
1252 KB |
Output is correct |
| 11 |
Correct |
447 ms |
1236 KB |
Output is correct |
| 12 |
Correct |
103 ms |
1108 KB |
Output is correct |
| 13 |
Correct |
881 ms |
1304 KB |
Output is correct |
| 14 |
Correct |
868 ms |
1296 KB |
Output is correct |
| 15 |
Correct |
847 ms |
1304 KB |
Output is correct |
| 16 |
Correct |
878 ms |
1356 KB |
Output is correct |
| 17 |
Correct |
857 ms |
1308 KB |
Output is correct |
| 18 |
Correct |
223 ms |
1012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1396 ms |
1284 KB |
3rd lines differ - on the 696th token, expected: '0', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
763 ms |
1284 KB |
Output is correct |
| 2 |
Correct |
1145 ms |
1300 KB |
Output is correct |
| 3 |
Correct |
1226 ms |
1236 KB |
Output is correct |
| 4 |
Correct |
1293 ms |
1196 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
89 ms |
852 KB |
Output is correct |
| 7 |
Correct |
44 ms |
880 KB |
Output is correct |
| 8 |
Correct |
5 ms |
852 KB |
Output is correct |
| 9 |
Correct |
37 ms |
852 KB |
Output is correct |
| 10 |
Correct |
4 ms |
468 KB |
Output is correct |
| 11 |
Correct |
64 ms |
832 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
662 ms |
932 KB |
3rd lines differ - on the 22nd token, expected: '0', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
