제출 #681971

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
681971		jophyyjh	장난감 기차 (IOI17_train)	C++14	100 / 100	1311 ms	1368 KiB

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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 12 / 12
• Subtask 6: 51 / 51