Submission #607176

#	Time	Username	Problem	Language	Result	Execution time	Memory
607176		jophyyjh	One-Way Streets (CEOI17_oneway)	C++14	60 / 100	3049 ms	20428 KiB

oneway

/**
 * Notes during contest.
 * 
 * ------ A ------
 * Looks like that it's about strongly-connected components, cycles or bridges. I
 * think we can detect all cycles and merge all those nodes into one. The resulting
 * graph would be a tree, so we can then use a difference array to find each edge's
 * direction. Note that any edge in a cycle is B, and any edge not in cycles is a
 * "bridge".
 *          !IMPORTANT! (Reminded by tinjyu during contest) !IMPORTANT!
 *                          Graph may not be CONNECTED.
 * 
 * ------ B ------
 * We iterate through all cost k. We can take at most k bets. If we can guarantee
 * a profit of p, min(#A_is_the_outcome, #B_is_the_outcome) >= p + k. Binary search
 * is ok.
 * For each k, we wanna find the max achievable for
 * min(#A_is_outcome, #B_is_outcome) - k.
 * 
 * ------ C ------
 * 
 * Time Complexity 1: O((n + m) * p)
 * Time Complexity 2: O(n * log(n * VAL_MAX) * log(n))
 * Time Complexity 3: O()
 * Implementation 0.7       (Solves [S1-2])
*/
 
#include <bits/stdc++.h>
 
typedef int64_t     int_t;
typedef std::vector<int_t>  vec;
 
const int_t INF = 0x3f3f3f3f3f3f;
 
// a DSU impl that allows assigning a value to each set
struct DSU {
    vec set, rank;
    int_t components;
    DSU(int_t n) {
        set.resize(n);
        rank.resize(n);
        for (int_t k = 0; k < n; k++)
            set[k] = k, rank[k] = 1;
        components = n;
    }
    inline int_t find(int_t k) {
        if (set[k] == k)
            return k;
        return set[k] = find(set[k]);
    }
    bool merge(int_t a, int_t b) {      // merge b into a   (keep a's value)
        a = find(a), b = find(b);
        if (a == b)
            return false;
        if (rank[b] > rank[a])
            std::swap(a, b);
        set[b] = a, rank[a] += rank[b], components--;
        return true;
    }
};
 
 
struct edge_t {
    int_t a, b;
};
 
struct neighb_t {
    int_t neighb, edge_idx;
};
 
typedef std::vector<neighb_t>   adj_list_t;
 
 
void dfs1(int_t k, int_t parent, const std::vector<adj_list_t>& graph,
            std::vector<bool>& tree_edge, vec& depth, std::vector<bool>& visited) {
    visited[k] = true;
    if (parent != -1)
        depth[k] = depth[parent] + 1;
    else
        depth[k] = 0;
    for (const neighb_t& child : graph[k]) {
        if (child.neighb == parent || visited[child.neighb])
            continue;
        tree_edge[child.edge_idx] = true;
        dfs1(child.neighb, k, graph, tree_edge, depth, visited);
    }
}
 
void dfs2(int_t k, int_t parent, const std::vector<adj_list_t>& graph,
                const std::vector<bool>& tree_edge, vec& across, const vec& depth,
                std::vector<bool>& is_bridge) {
    across[k] = 0;
    int_t backward_up = 0, backward_down = 0;
    for (const neighb_t& child : graph[k]) {
        if (tree_edge[child.edge_idx] && child.neighb != parent) {
            dfs2(child.neighb, k, graph, tree_edge, across, depth, is_bridge);
            across[k] += across[child.neighb];
        } else {
            if (depth[child.neighb] > depth[k])
                backward_down++;
            else if (depth[child.neighb] < depth[k])
                backward_up++;
        }
    }
    if (parent != -1)   // the tree edge linking to parent
        backward_up--;
    across[k] += backward_up - backward_down;
    assert(across[k] >= 0);
    if (parent != -1 && across[k] == 0) {
        for (const neighb_t& child : graph[k]) {
            if (child.neighb == parent)
                is_bridge[child.edge_idx] = true;
        }
    }
}
 
// Find bridges in the graph with a DFS tree
// I learnt this from a tutorial on codeforces (about DFS trees)
std::vector<bool> find_bridge(int_t n, int_t m,
                                    const std::vector<edge_t>& original_graph) {
    std::vector<adj_list_t> graph(n);
    for (int_t k = 0; k < m; k++) {
        int_t a = original_graph[k].a, b = original_graph[k].b;
        graph[a].push_back(neighb_t{b, k});
        graph[b].push_back(neighb_t{a, k});
    }
    vec depth(n), across(n);
    std::vector<bool> tree_edge(m, false);
    std::vector<bool> visited(n, false);
    std::vector<bool> is_bridge(m, false);
    for (int_t k = 0; k < n; k++) {
        if (!visited[k]) {
            dfs1(k, -1, graph, tree_edge, depth, visited);
            dfs2(k, -1, graph, tree_edge, across, depth, is_bridge);
        }
    }
    return is_bridge;
}
 
int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    int_t n, m;
    std::cin >> n >> m;
    std::vector<edge_t> original_graph(m);
    for (int_t k = 0; k < m; k++) {
        std::cin >> original_graph[k].a >> original_graph[k].b;
        original_graph[k].a--, original_graph[k].b--;
    }
 
 
    std::vector<bool> is_bridge = find_bridge(n, m, original_graph);
    std::cerr << "[debug] is_bridge[]: ";
    for (int_t k = 0; k < m; k++)
        std::cerr << is_bridge[k];
    std::cerr << std::endl;
 
    DSU compress(n);    // used to compress the nodes
    for (int_t k = 0; k < m; k++) {
        if (!is_bridge[k])
            compress.merge(original_graph[k].a, original_graph[k].b);
    }
    vec map(n, -1);         // mapping an original node into one in our new graph
    // std::cerr << "[debug] map[]: ";
    for (int_t k = 0, new_graph_top = 0; k < n; k++) {
        if (map[compress.find(k)] == -1)
            map[compress.find(k)] = new_graph_top++;
        map[k] = map[compress.find(k)];
        // std::cerr << map[k] << ' ';
    }
    // std::cerr << std::endl;
    std::vector<adj_list_t> graph(compress.components);
    for (int_t k = 0; k < m; k++) {
        int_t a = map[original_graph[k].a], b = map[original_graph[k].b];
        if (a != b) {
            graph[a].push_back(neighb_t{b, k});
            graph[b].push_back(neighb_t{a, k});
        }
    }
    n = compress.components;
 
    int_t pairs;
    std::cin >> pairs;
    vec start(m, -1);   // for each edge, if it's a -> b, start[] = a.
    for (int_t k = 0; k < pairs; k++) {
        int_t src, dst;
        std::cin >> src >> dst;
        src = map[src - 1], dst = map[dst - 1];
        if (src == dst)
            continue;
        // TODO: improve BFS
        std::queue<int_t> bfs_queue;
        std::vector<int_t> edge_num(n, -1), prev(n, -1);
        edge_num[src] = INF;    // doesn't exist. Anything not -1 would be good
        bfs_queue.emplace(src);
        while (!bfs_queue.empty()) {
            int_t t = bfs_queue.front();
            bfs_queue.pop();
            if (t == dst)
                break;
            for (const neighb_t& e : graph[t]) {
                if (edge_num[e.neighb] != -1)
                    continue;
                edge_num[e.neighb] = e.edge_idx, prev[e.neighb] = t;
                bfs_queue.push(e.neighb);
            }
        }
        for (int_t pt = dst; pt != src; pt = prev[pt]) {
            assert(edge_num[pt] != -1);
            start[edge_num[pt]] = prev[pt];
        }
    }
 
    std::string ans(m, '@');
    for (int_t k = 0; k < m; k++) {
        if (is_bridge[k]) {
            if (start[k] != -1) {
                if (map[original_graph[k].a] == start[k])
                    ans[k] = 'R';
                else
                    ans[k] = 'L';
            } else {
                ans[k] = 'B';
            }
        } else {
            ans[k] = 'B';
        }
    }
    std::cout << ans << '\n';
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40