Submission #434618

#	Time	Username	Problem	Language	Result	Execution time	Memory
434618		KoD	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	324 ms	28356 KiB

oneway

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40