oj.uz

Submission #607176

# Submission time Handle Problem Language Result Execution time Memory
607176 2022-07-26T12:47:26 Z jophyyjh One-Way Streets (CEOI17_oneway) C++14
60 / 100
 3000 ms 20428 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.
 * 
 * ------ 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.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 516 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 167 ms 11052 KB Output is correct
12 Correct 200 ms 12516 KB Output is correct
13 Correct 169 ms 14380 KB Output is correct
14 Correct 185 ms 16000 KB Output is correct
15 Correct 216 ms 16488 KB Output is correct
16 Correct 217 ms 15448 KB Output is correct
17 Correct 649 ms 18324 KB Output is correct
18 Correct 793 ms 15560 KB Output is correct
19 Correct 529 ms 20428 KB Output is correct
20 Correct 181 ms 11980 KB Output is correct
21 Correct 153 ms 11460 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 516 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 167 ms 11052 KB Output is correct
12 Correct 200 ms 12516 KB Output is correct
13 Correct 169 ms 14380 KB Output is correct
14 Correct 185 ms 16000 KB Output is correct
15 Correct 216 ms 16488 KB Output is correct
16 Correct 217 ms 15448 KB Output is correct
17 Correct 649 ms 18324 KB Output is correct
18 Correct 793 ms 15560 KB Output is correct
19 Correct 529 ms 20428 KB Output is correct
20 Correct 181 ms 11980 KB Output is correct
21 Correct 153 ms 11460 KB Output is correct
22 Execution timed out 3049 ms 18444 KB Time limit exceeded
23 Halted 0 ms 0 KB -