답안 #681971

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
681971	2023-01-15T02:33:51 Z	jophyyjh	장난감 기차 (IOI17_train)	C++14	100 / 100	1311 ms	1368 KB

train

/**
 * 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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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