Submission #855968

#	Time	Username	Problem	Language	Result	Execution time	Memory
855968		Cyanmond	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	129 ms	37120 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define per(i, l, r) for (int i = (r - 1); i >= l; --i)
#define ALL(x) (x).begin(), (x).end()

using i64 = long long;

vector<int> decomposite(const vector<vector<pair<int, int>>> &graph) {
    const int n = (int)graph.size();
    vector<bool> isUsed(n);
    vector<int> ord(n), low(n);

    auto dfs = [&](auto &&self, const int v, const int p, int &id) -> void {
        isUsed[v] = true;
        ord[v] = id++;
        low[v] = ord[v];
        for (const auto &[t, i] : graph[v]) {
            if (isUsed[t]) {
                if (i != p) low[v] = min(low[v], ord[t]);
                continue;
            }
            self(self, t, i, id);
            low[v] = min(low[v], low[t]);
        }
    };
    int id = 0;
    rep(i, 0, n) {
        if (not isUsed[i]) {
            dfs(dfs, i, -1, id);
        }
    }

    vector<int> group(n, -1);
    auto dfs2 = [&](auto &&self, const int v, const int p, int &id) -> void {
        assert(group[v] == -1);
        if (p != -1 and ord[p] >= low[v]) {
            group[v] = group[p];
        } else {
            group[v] = id++;
        }
        for (const auto &[t, i] : graph[v]) {
            if (group[t] != -1) continue;
            self(self, t, v, id);
        }
    };
    id = 0;
    rep(i, 0, n) {
        if (group[i] == -1) {
            dfs2(dfs2, i, -1, id);
        }
    }
    return group;
}

void main_() {
    int N, M;
    cin >> N >> M;
    vector<int> A(M), B(M);
    vector<vector<pair<int, int>>> graph(N);
    rep(i, 0, M) {
        cin >> A[i] >> B[i];
        graph[--A[i]].push_back({--B[i], i});
        graph[B[i]].push_back({A[i], i});
    }
    int P;
    cin >> P;
    vector<int> X(P), Y(P);
    rep(i, 0, P) {
        cin >> X[i] >> Y[i];
        --X[i], --Y[i];
    }

    const auto group = decomposite(graph);
    vector<char> ans(M, 'A');
    rep(i, 0, M) {
        if (group[A[i]] == group[B[i]]) {
            ans[i] = 'B';
        }
    }

    const int U = *max_element(ALL(group)) + 1;
    vector<vector<pair<int, int>>> tree(U);
    rep(i, 0, M) {
        if (group[A[i]] != group[B[i]]) {
            tree[group[A[i]]].push_back({group[B[i]], i});
            tree[group[B[i]]].push_back({group[A[i]], i});
        }
    }

    vector<vector<int>> F(N), T(N);
    rep(i, 0, P) {
        F[X[i]].push_back(i);
        T[Y[i]].push_back(i);
    }

    vector<int> par(U, -1), depth(U);
    constexpr int R = 20;
    vector<vector<int>> table(R);
    auto dfsC = [&](auto &&self, const int v, const int p, const int d) -> void {
        par[v] = p;
        depth[v] = d;
        for (const auto &[t, i] : tree[v]) {
            if (t == p) continue;
            self(self, t, v, d + 1);
        }
    };
    rep(i, 0, U) {
        if (par[i] != -1) continue;
        dfsC(dfsC, i, -1, 0);
    }

    table[0] = par;
    rep(rank, 1, R) {
        table[rank].assign(U, -1);
        rep(i, 0, U) {
            if (table[rank - 1][i] == -1) continue;
            else table[rank][i] = table[rank - 1][table[rank - 1][i]];
        }
    }

    auto calcLCA = [&](int u, int v) {
        if (depth[u] > depth[v]) swap(u, v);
        per(rank, 0, 20) {
            const int a = table[rank][v];
            if (a != -1 and depth[a] >= depth[u]) v = a;
        }
        assert(depth[u] == depth[v]);
        if (u == v) return u;
        per(rank, 0, 20) {
            const int a = table[rank][u], b = table[rank][v];
            if (a != b) {
                u = a;
                v = b;
            }
        }
        assert(par[u] == par[v]);
        return par[u];
    };

    vector<int> e1(U), e2(U);
    rep(i, 0, P) {
        const int lca = calcLCA(group[X[i]], group[Y[i]]);
        ++e1[group[X[i]]];
        ++e2[group[Y[i]]];
        --e1[lca];
        --e2[lca];
    }

    auto setVal = [&](int a, int b, int i, int v) {
        if (group[A[i]] != a) {
            // rev
            if (v != 3) v ^= 3;
        }
        ans[i] = v == 1 ? 'R' : (v == 2 ? 'L' : 'B');
    };

    vector<bool> isUsed(U);
    auto dfs = [&](auto &&self, const int v, const int p) -> pair<int, int> {
        isUsed[v] = true;
        pair<int, int> val = {e1[v], e2[v]};
        for (const auto &[t, i] : tree[v]) {
            if (t == p) continue;
            const auto res = self(self, t, v);
            {
                if (res.first != 0) setVal(t, v, i, 1);
                else if (res.second != 0) setVal(v, t, i, 1);
                else setVal(v, t, i, 3);
            }
            val.first += res.first;
            val.second += res.second;
        }
        return val;
    };
    rep(i, 0, U) {
        if (not isUsed[i]) {
            dfs(dfs, i, -1);
        }
    }

    for (const auto e : ans) cout << e;
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    main_();
}

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