Submission #1330606

#TimeUsernameProblemLanguageResultExecution timeMemory
1330606i_am_blindfoldOne-Way Streets (CEOI17_oneway)C++20
100 / 100
137 ms31620 KiB
#include <bits/stdc++.h>
using namespace std;

const int LOG = 20;

struct DSU {
    DSU() {}
    void build(int N) {
        P.resize(N + 1, 0);
    }
    vector<int> P;
    int find(int a) {
        if (P[a] == 0) return a;
        return P[a] = find(P[a]);
    }
    void unite(int a, int b) {
        a = find(a), b = find(b);
        if (a == b) return;
        P[b] = a;
    }
};

struct Graph_with_Tarjan {
    Graph_with_Tarjan(int N, int M) {
        mrk.resize(M + 1, 0);
        vis.resize(N + 1, 0);
        bck.resize(M + 1, 0);
        adj.resize(N + 1);
        tin.resize(N + 1);
        low.resize(N + 1);
    }
    vector<vector<pair<int, int>>> adj;
    vector<int> mrk, tin, low, vis, bck;
    void add_edge(int u, int v, int i) {
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    void dfs(int u, int ip, int& t) {
        tin[u] = low[u] = t++, vis[u] = 1;
        for (auto &[v, i]: adj[u]) {
            if (i == ip) continue;
            if (!vis[v]) {
                dfs(v, i, t);
                low[u] = min(low[u], low[v]);
                if (low[v] > tin[u]) {
                    mrk[i] = 1;
                }
            } else {
                low[u] = min(low[u], tin[v]);
                bck[i] = 1;
            }
        }
    }
};

struct Tree_with_LCA {
    Tree_with_LCA(int N, int M) {
        up.resize(N + 1, vector<int>(LOG, 0));
        mrk.resize(M + 1, 0);
        vis.resize(N + 1, 0);
        adj.resize(N + 1);
        dep.resize(N + 1);
        id.resize(N + 1);
        dsu.build(N);
    }
    vector<vector<pair<int, int>>> adj;
    vector<vector<int>> up;
    vector<int> dep, mrk, id, vis;
    DSU dsu;
    void add_edge(int u, int v, int i) {
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    void dfs(int u, int p, int d) {
        dep[u] = d, up[u][0] = p, vis[u] = 1;
        for (auto &[v, i]: adj[u]) {
            if (v == p) continue;
            id[v] = i;
            dfs(v, u, d + 1);
        }
    }
    void build(int n) {
        for (int i = 1; i < LOG; i++) {
            for (int u = 1; u <= n; u++) {
                up[u][i] = up[up[u][i - 1]][i - 1];
            }
        }
    }
    int lift(int u, int x) {
        for (int i = LOG - 1; i >= 0; i--) {
            if (x & (1 << i)) {
                u = up[u][i];
            }
        }
        return u;
    }
    int LCA(int u, int v) {
        if (dep[u] < dep[v]) swap(u, v);
        u = lift(u, dep[u] - dep[v]);
        if (u == v) return u;
        for (int i = LOG - 1; i >= 0; i--) {
            if (up[u][i] != up[v][i]) {
                u = up[u][i], v = up[v][i];
            }
        }
        return up[u][0];
    }
    void update(int u, int v, int x) {
        while (dep[u = dsu.find(u)] > dep[v]) {
            mrk[id[u]] = x;
            dsu.unite(v, u);
            u = up[u][0];
        }
    }
};

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

    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> edge(m);
    for (auto &[u, v]: edge) {
        cin >> u >> v;
    } 

    Graph_with_Tarjan graph(n, m);

    for (int i = 0; i < m; i++) {
        auto [u, v] = edge[i];
        graph.add_edge(u, v, i);
    }

    for (int i = 1, t = 0; i <= n; i++) {
        if (!graph.vis[i]) {
            graph.dfs(i, - 1, t);
        }
    }

    Tree_with_LCA tree(n, m);

    for (int i = 0; i < m; i++) {
        if (!graph.bck[i]) {
            auto [u, v] = edge[i];
            tree.add_edge(u, v, i);
        }
    }

    for (int i = 1; i <= n; i++) {
        if (!tree.vis[i]) {
            tree.dfs(i, 0, 0);
        }
    }

    tree.build(n);

    int q;
    cin >> q;

    while (q--) {
        int u, v;
        cin >> u >> v;

        int lca = tree.LCA(u, v);

        tree.update(u, lca, 1);
        tree.update(v, lca, 2);
    }

    for (int i = 0; i < m; i++) {
        if (graph.mrk[i]) {
            auto [u, v] = edge[i];
            if (tree.mrk[i] == 0) {
                cout << 'B';
            } else if (tree.mrk[i] == 1) {
                if (v == tree.up[u][0]) {
                    cout << 'R';
                } else {
                    cout << 'L';
                }
            } else {
                if (v == tree.up[u][0]) {
                    cout << 'L';
                } else {
                    cout << 'R';
                }
            }
        } else {
            cout << 'B';
        }
    }
    cout << '\n';

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...