Submission #434608

#	Time	Username	Problem	Language	Result	Execution time	Memory
434608		KoD	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	1 ms	204 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<int>> graph(N);
    std::map<std::pair<int, int>, int> eid;
    std::map<std::pair<int, int>, bool> rev;
    for (int i = 0; i < M; ++i) {
        int x, y;
        std::cin >> x >> y;
        x -= 1;
        y -= 1;
        graph[x].push_back(y);
        graph[y].push_back(x);
        eid[{x, y}] = eid[{y, x}] = i;
        rev[{y, x}] = true;
    }
    Vec<Vec<int>> children(N);
    Vec<int> sum(N), parent(N), depth(N, -1);
    auto dfs = [&](auto&& dfs, const int u) -> void {
        for (const int v : graph[u]) {
            if (v != parent[u]) {
                if (depth[v] == -1) {
                    parent[v] = u;
                    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;
                }
            }
        }
    };
    depth[0] = 0;
    dfs(dfs, 0);
    std::array<Vec<int>, 17> lift;
    lift[0] = parent;
    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&& dfs, const int u) -> void {
        for (const int v : children[u]) {
            dfs(dfs, v);
            xs[u] += xs[v];
            ys[u] += ys[v];
        }
    };
    count(count, 0);
    std::string ans(M, 'B');
    for (int u = 1; u < N; ++u) {
        if (sum[u] == 0) {
            const std::pair<int, int> e(u, parent[u]);
            if (xs[u] > 0) {
                ans[eid[e]] = rev[e] ? 'L' : 'R';
            }
            if (ys[u] > 0) {
                ans[eid[e]] = rev[e] ? 'R' : 'L';
            }
        }
    }
    std::cout << ans << '\n';
    return 0;
}

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