oj.uz

Submission #434618

# Submission time Handle Problem Language Result Execution time Memory
434618 2021-06-21T13:16:10 Z KoD One-Way Streets (CEOI17_oneway) C++17
100 / 100
 324 ms 28356 KB 
#include <bits/stdc++.h>

template <class T> using Vec = std::vector<T>;

int main() {
    int N, M;
    std::cin >> N >> M;
    Vec<Vec<std::pair<int, int>>> graph(N);
    Vec<int> A(M), B(M);
    for (int i = 0; i < M; ++i) {
        std::cin >> A[i] >> B[i];
        A[i] -= 1;
        B[i] -= 1;
        graph[A[i]].emplace_back(B[i], i);
        graph[B[i]].emplace_back(A[i], i);
    }
    Vec<Vec<int>> children(N);
    Vec<int> sum(N), parent(N, -1), depth(N, -1);
    auto dfs = [&](auto&& dfs, const int u) -> void {
        for (const auto [v, e] : graph[u]) {
            if (e != parent[u]) {
                if (depth[v] == -1) {
                    parent[v] = e;
                    depth[v] = depth[u] + 1;
                    children[u].push_back(v);
                    dfs(dfs, v);
                    sum[u] += sum[v];
                } else if (depth[v] < depth[u]) {
                    sum[u] += 1;
                    sum[v] -= 1;
                }
            }
        }
    };
    Vec<int> roots;
    for (int i = 0; i < N; ++i) {
        if (depth[i] == -1) {
            depth[i] = 0;
            dfs(dfs, i);
            roots.push_back(i);
        }
    }
    depth[0] = 0;
    dfs(dfs, 0);
    std::array<Vec<int>, 17> lift;
    lift[0].resize(N);
    for (int i = 0; i < N; ++i) {
        lift[0][i] = parent[i] == -1 ? i : (A[parent[i]] == i ? B[parent[i]] : A[parent[i]]);
    }
    for (int i = 0; i < 16; ++i) {
        lift[i + 1].resize(N);
        for (int j = 0; j < N; ++j) {
            lift[i + 1][j] = lift[i][lift[i][j]];
        }
    }
    const auto lca = [&](int x, int y) {
        if (depth[x] > depth[y]) {
            std::swap(x, y);
        }
        const int dif = depth[y] - depth[x];
        for (int i = 0; i < 17; ++i) {
            if (dif >> i & 1) {
                y = lift[i][y];
            }
        }
        if (x == y) {
            return x;
        }
        for (int i = 16; i >= 0; --i) {
            if (lift[i][x] != lift[i][y]) {
                x = lift[i][x];
                y = lift[i][y];
            }
        }
        return lift[0][x];
    };
    int P;
    std::cin >> P;
    Vec<int> xs(N), ys(N);
    for (int i = 0; i < P; ++i) {
        int x, y;
        std::cin >> x >> y;
        x -= 1;
        y -= 1;
        const int z = lca(x, y);
        xs[x] += 1;
        xs[z] -= 1;
        ys[y] += 1;
        ys[z] -= 1;
    }
    auto count = [&](auto&& count, const int u) -> void {
        for (const int v : children[u]) {
            count(count, v);
            xs[u] += xs[v];
            ys[u] += ys[v];
        }
    };
    for (const int r : roots) {
        count(count, r);
    }
    std::string ans(M, 'B');
    for (int u = 0; u < N; ++u) {
        if (parent[u] != -1 and sum[u] == 0) {
            const int e = parent[u];
            if (xs[u] > 0) {
                ans[e] = (B[e] == u) ? 'L' : 'R';
            }
            if (ys[u] > 0) {
                ans[e] = (B[e] == u) ? 'R' : 'L';
            }
        }
    }
    std::cout << ans << '\n';
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 424 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 2 ms 428 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 424 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 2 ms 428 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 100 ms 9036 KB Output is correct
12 Correct 109 ms 11864 KB Output is correct
13 Correct 128 ms 15820 KB Output is correct
14 Correct 159 ms 20688 KB Output is correct
15 Correct 158 ms 22080 KB Output is correct
16 Correct 165 ms 21024 KB Output is correct
17 Correct 165 ms 23416 KB Output is correct
18 Correct 134 ms 21008 KB Output is correct
19 Correct 181 ms 24792 KB Output is correct
20 Correct 125 ms 14476 KB Output is correct
21 Correct 96 ms 14148 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 424 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 3 ms 460 KB Output is correct
8 Correct 2 ms 428 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 100 ms 9036 KB Output is correct
12 Correct 109 ms 11864 KB Output is correct
13 Correct 128 ms 15820 KB Output is correct
14 Correct 159 ms 20688 KB Output is correct
15 Correct 158 ms 22080 KB Output is correct
16 Correct 165 ms 21024 KB Output is correct
17 Correct 165 ms 23416 KB Output is correct
18 Correct 134 ms 21008 KB Output is correct
19 Correct 181 ms 24792 KB Output is correct
20 Correct 125 ms 14476 KB Output is correct
21 Correct 96 ms 14148 KB Output is correct
22 Correct 312 ms 24640 KB Output is correct
23 Correct 307 ms 22532 KB Output is correct
24 Correct 324 ms 22212 KB Output is correct
25 Correct 268 ms 28356 KB Output is correct
26 Correct 269 ms 24004 KB Output is correct
27 Correct 263 ms 22596 KB Output is correct
28 Correct 93 ms 4444 KB Output is correct
29 Correct 203 ms 15140 KB Output is correct
30 Correct 199 ms 15260 KB Output is correct
31 Correct 206 ms 15652 KB Output is correct
32 Correct 241 ms 20128 KB Output is correct