oj.uz

Submission #607246

# Submission time Handle Problem Language Result Execution time Memory
607246 2022-07-26T13:56:13 Z jophyyjh One-Way Streets (CEOI17_oneway) C++14
100 / 100
 127 ms 24196 KB 
/**
 * 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.
 * [After contest] I realized that i forgot how to use a difference array on a tree.
 * That's why i couldn't solve the last testcase. Noooo..
 * 
 * PS1  I think this is the problem for which i wrote the most code.. In general, I
 * think CEOI 2017 Day 1 is more technical, instead of requiring ingenius thoughts.
 * PS2  It turns out that we don't even need to compute LCA. (+1/-1 cancels out)
 * 
 * ------ 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 ------
 * We have a tree in which a mouse runs. [S1] is just a brute-force.
 * 
 * Time Complexity 1: O(n + m + p)
 * Time Complexity 2: O(n * log(n * VAL_MAX) * log(n))
 * Time Complexity 3: O()
 * Implementation 1
*/
 
#include <bits/stdc++.h>
 
typedef int64_t     int_t;
typedef std::vector<int_t>  vec;
 
const int_t INF = 0x3f3f3f3f3f3f;
const int_t LCA_HEIGHT = 18;
 
inline int_t log2(int_t k)  { return sizeof(int_t) * 8 - __builtin_clzll(k) - 1; }
 
// 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_t dfs3(int_t k, int_t parent, const std::vector<adj_list_t>& graph,
                std::vector<bool>& visited, const vec& diff, vec& start) {
    visited[k] = true;
    int_t sum = 0, up_edge = -1;
    for (const neighb_t& neighb : graph[k]) {
        if (neighb.neighb == parent) {
            up_edge = neighb.edge_idx;
        } else {
            sum += dfs3(neighb.neighb, k, graph, visited, diff, start);
        }
    }
    sum += diff[k];
    if (sum > 0)
        start[up_edge] = parent;
    else if (sum < 0)
        start[up_edge] = k;
    return sum;
}
 
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);
    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
    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::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 diff(n, 0);         // difference array on a tree
    for (int_t k = 0; k < pairs; k++) {
        int_t src, dst;
        std::cin >> src >> dst;
        src = map[src - 1], dst = map[dst - 1];
        diff[src]--, diff[dst]++;
    }
    std::vector<bool> visited(n, false);
    vec start(m, -1);       // start[]: edge a -> b, start = a.
    for (int_t k = 0; k < n; k++) {
        if (!visited[k])
            dfs3(k, -1, graph, visited, diff, start);
    }
 
    std::string ans(m, 'B');
    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';
            }
        }
    }
    std::cout << ans << '\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 35 ms 9976 KB Output is correct
12 Correct 38 ms 11500 KB Output is correct
13 Correct 54 ms 13248 KB Output is correct
14 Correct 65 ms 14736 KB Output is correct
15 Correct 75 ms 15244 KB Output is correct
16 Correct 89 ms 13464 KB Output is correct
17 Correct 78 ms 16388 KB Output is correct
18 Correct 98 ms 13468 KB Output is correct
19 Correct 94 ms 18400 KB Output is correct
20 Correct 56 ms 10872 KB Output is correct
21 Correct 39 ms 10316 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 35 ms 9976 KB Output is correct
12 Correct 38 ms 11500 KB Output is correct
13 Correct 54 ms 13248 KB Output is correct
14 Correct 65 ms 14736 KB Output is correct
15 Correct 75 ms 15244 KB Output is correct
16 Correct 89 ms 13464 KB Output is correct
17 Correct 78 ms 16388 KB Output is correct
18 Correct 98 ms 13468 KB Output is correct
19 Correct 94 ms 18400 KB Output is correct
20 Correct 56 ms 10872 KB Output is correct
21 Correct 39 ms 10316 KB Output is correct
22 Correct 95 ms 17328 KB Output is correct
23 Correct 111 ms 15884 KB Output is correct
24 Correct 122 ms 15784 KB Output is correct
25 Correct 127 ms 24196 KB Output is correct
26 Correct 106 ms 18044 KB Output is correct
27 Correct 98 ms 15992 KB Output is correct
28 Correct 27 ms 6716 KB Output is correct
29 Correct 58 ms 12072 KB Output is correct
30 Correct 55 ms 11948 KB Output is correct
31 Correct 59 ms 12516 KB Output is correct
32 Correct 64 ms 15764 KB Output is correct