/**
* 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.
*
* Let's now solve the whole problem.
*
* Time Complexity: O(n + m)
* Implementation 0.9 (Just a test)
*/
#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();
std::vector<vec> graph(n), rev_graph(n);
vec out_original(n, 0);
for (int e = 0; e < m; e++) {
graph[u[e]].push_back(v[e]);
rev_graph[v[e]].push_back(u[e]);
out_original[u[e]]++;
}
std::vector<bool> reach(n, false);
std::queue<int> bfs_queue;
for (int k = 0; k < n; k++) {
if (charge[k]) {
reach[k] = true;
bfs_queue.push(k);
}
}
vec out_deg = out_original;
while (!bfs_queue.empty()) {
int t = bfs_queue.front();
bfs_queue.pop();
for (int prev : rev_graph[t]) {
if (reach[prev])
continue;
out_deg[prev]--;
if ((owner[prev] == 0 && out_deg[prev] == 0) || owner[prev] == 1) {
reach[prev] = true;
bfs_queue.push(prev);
}
}
}
vec can_win(n, 0);
for (int k = 0; k < n; k++) {
if (!charge[k])
continue;
bool cycle;
if (owner[k] == 1) {
cycle = false;
for (int neighb : graph[k])
cycle |= reach[neighb];
} else {
cycle = true;
for (int neighb : graph[k])
cycle &= reach[neighb];
}
if (cycle) {
can_win[k] = 1;
bfs_queue.push(k);
}
}
out_deg = out_original;
while (!bfs_queue.empty()) {
int t = bfs_queue.front();
bfs_queue.pop();
for (int prev : rev_graph[t]) {
if (can_win[prev])
continue;
out_deg[prev]--;
if ((owner[prev] == 0 && out_deg[prev] == 0) || owner[prev] == 1) {
can_win[prev] = 1;
bfs_queue.push(prev);
}
}
}
return can_win;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1108 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
300 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
300 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
3rd lines differ - on the 4th token, expected: '0', found: '1' |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
1592 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1364 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1468 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
1492 KB |
3rd lines differ - on the 108th token, expected: '0', found: '1' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1588 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1580 KB |
Output is correct |
| 3 |
Correct |
8 ms |
1620 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1084 KB |
Output is correct |
| 7 |
Correct |
5 ms |
980 KB |
Output is correct |
| 8 |
Correct |
5 ms |
980 KB |
Output is correct |
| 9 |
Correct |
5 ms |
956 KB |
Output is correct |
| 10 |
Correct |
2 ms |
468 KB |
Output is correct |
| 11 |
Correct |
5 ms |
852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1108 KB |
3rd lines differ - on the 1st token, expected: '0', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
