oj.uz

Submission #681971

# Submission time Handle Problem Language Result Execution time Memory
681971 2023-01-15T02:33:51 Z jophyyjh Toy Train (IOI17_train) C++14
100 / 100
 1311 ms 1368 KB 
/**
 * 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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 852 KB Output is correct
2 Correct 423 ms 924 KB Output is correct
3 Correct 443 ms 852 KB Output is correct
4 Correct 412 ms 972 KB Output is correct
5 Correct 422 ms 852 KB Output is correct
6 Correct 427 ms 972 KB Output is correct
7 Correct 174 ms 920 KB Output is correct
8 Correct 659 ms 924 KB Output is correct
9 Correct 433 ms 900 KB Output is correct
10 Correct 429 ms 884 KB Output is correct
11 Correct 389 ms 884 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 300 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 300 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 1316 KB Output is correct
2 Correct 176 ms 1328 KB Output is correct
3 Correct 189 ms 1324 KB Output is correct
4 Correct 934 ms 1288 KB Output is correct
5 Correct 620 ms 1296 KB Output is correct
6 Correct 108 ms 1296 KB Output is correct
7 Correct 1036 ms 1312 KB Output is correct
8 Correct 388 ms 1288 KB Output is correct
9 Correct 91 ms 1252 KB Output is correct
10 Correct 664 ms 1252 KB Output is correct
11 Correct 492 ms 1228 KB Output is correct
12 Correct 93 ms 1192 KB Output is correct
13 Correct 941 ms 1296 KB Output is correct
14 Correct 957 ms 1300 KB Output is correct
15 Correct 946 ms 1308 KB Output is correct
16 Correct 979 ms 1300 KB Output is correct
17 Correct 907 ms 1300 KB Output is correct
18 Correct 221 ms 980 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 929 ms 1148 KB Output is correct
2 Correct 827 ms 1180 KB Output is correct
3 Correct 133 ms 1276 KB Output is correct
4 Correct 90 ms 1296 KB Output is correct
5 Correct 597 ms 1244 KB Output is correct
6 Correct 875 ms 1276 KB Output is correct
7 Correct 820 ms 1356 KB Output is correct
8 Correct 109 ms 1368 KB Output is correct
9 Correct 819 ms 1244 KB Output is correct
10 Correct 1147 ms 1332 KB Output is correct
11 Correct 1090 ms 1344 KB Output is correct
12 Correct 1161 ms 1364 KB Output is correct
13 Correct 685 ms 1276 KB Output is correct
14 Correct 866 ms 1236 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 772 ms 1284 KB Output is correct
2 Correct 1180 ms 1356 KB Output is correct
3 Correct 1168 ms 1364 KB Output is correct
4 Correct 1270 ms 1216 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 90 ms 860 KB Output is correct
7 Correct 43 ms 972 KB Output is correct
8 Correct 5 ms 824 KB Output is correct
9 Correct 37 ms 852 KB Output is correct
10 Correct 3 ms 372 KB Output is correct
11 Correct 68 ms 832 KB Output is correct

Subtask #6
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 852 KB Output is correct
2 Correct 423 ms 924 KB Output is correct
3 Correct 443 ms 852 KB Output is correct
4 Correct 412 ms 972 KB Output is correct
5 Correct 422 ms 852 KB Output is correct
6 Correct 427 ms 972 KB Output is correct
7 Correct 174 ms 920 KB Output is correct
8 Correct 659 ms 924 KB Output is correct
9 Correct 433 ms 900 KB Output is correct
10 Correct 429 ms 884 KB Output is correct
11 Correct 389 ms 884 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 304 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 0 ms 300 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 0 ms 300 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Correct 136 ms 1316 KB Output is correct
33 Correct 176 ms 1328 KB Output is correct
34 Correct 189 ms 1324 KB Output is correct
35 Correct 934 ms 1288 KB Output is correct
36 Correct 620 ms 1296 KB Output is correct
37 Correct 108 ms 1296 KB Output is correct
38 Correct 1036 ms 1312 KB Output is correct
39 Correct 388 ms 1288 KB Output is correct
40 Correct 91 ms 1252 KB Output is correct
41 Correct 664 ms 1252 KB Output is correct
42 Correct 492 ms 1228 KB Output is correct
43 Correct 93 ms 1192 KB Output is correct
44 Correct 941 ms 1296 KB Output is correct
45 Correct 957 ms 1300 KB Output is correct
46 Correct 946 ms 1308 KB Output is correct
47 Correct 979 ms 1300 KB Output is correct
48 Correct 907 ms 1300 KB Output is correct
49 Correct 221 ms 980 KB Output is correct
50 Correct 929 ms 1148 KB Output is correct
51 Correct 827 ms 1180 KB Output is correct
52 Correct 133 ms 1276 KB Output is correct
53 Correct 90 ms 1296 KB Output is correct
54 Correct 597 ms 1244 KB Output is correct
55 Correct 875 ms 1276 KB Output is correct
56 Correct 820 ms 1356 KB Output is correct
57 Correct 109 ms 1368 KB Output is correct
58 Correct 819 ms 1244 KB Output is correct
59 Correct 1147 ms 1332 KB Output is correct
60 Correct 1090 ms 1344 KB Output is correct
61 Correct 1161 ms 1364 KB Output is correct
62 Correct 685 ms 1276 KB Output is correct
63 Correct 866 ms 1236 KB Output is correct
64 Correct 772 ms 1284 KB Output is correct
65 Correct 1180 ms 1356 KB Output is correct
66 Correct 1168 ms 1364 KB Output is correct
67 Correct 1270 ms 1216 KB Output is correct
68 Correct 1 ms 340 KB Output is correct
69 Correct 90 ms 860 KB Output is correct
70 Correct 43 ms 972 KB Output is correct
71 Correct 5 ms 824 KB Output is correct
72 Correct 37 ms 852 KB Output is correct
73 Correct 3 ms 372 KB Output is correct
74 Correct 68 ms 832 KB Output is correct
75 Correct 180 ms 1280 KB Output is correct
76 Correct 205 ms 1236 KB Output is correct
77 Correct 231 ms 1332 KB Output is correct
78 Correct 233 ms 1236 KB Output is correct
79 Correct 231 ms 1328 KB Output is correct
80 Correct 1311 ms 1292 KB Output is correct
81 Correct 399 ms 1288 KB Output is correct
82 Correct 710 ms 1316 KB Output is correct
83 Correct 692 ms 1292 KB Output is correct
84 Correct 490 ms 1288 KB Output is correct
85 Correct 91 ms 1292 KB Output is correct
86 Correct 373 ms 1296 KB Output is correct
87 Correct 88 ms 1272 KB Output is correct
88 Correct 233 ms 1292 KB Output is correct
89 Correct 550 ms 1284 KB Output is correct
90 Correct 98 ms 1284 KB Output is correct
91 Correct 154 ms 1288 KB Output is correct
92 Correct 432 ms 1300 KB Output is correct
93 Correct 349 ms 1340 KB Output is correct
94 Correct 233 ms 1208 KB Output is correct
95 Correct 440 ms 1296 KB Output is correct
96 Correct 871 ms 1356 KB Output is correct
97 Correct 309 ms 1312 KB Output is correct
98 Correct 405 ms 1288 KB Output is correct
99 Correct 381 ms 1260 KB Output is correct
100 Correct 221 ms 996 KB Output is correct