제출 #670900

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
670900		jophyyjh	Toy Train (IOI17_train)	C++14	12 / 100	8 ms	1620 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.
 * 
 * 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;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 12 / 12
• Subtask 6: 0 / 51