Submission #1322669

#TimeUsernameProblemLanguageResultExecution timeMemory
1322669madamadam3One-Way Streets (CEOI17_oneway)C++20
0 / 100
3094 ms568 KiB
#include <bits/stdc++.h>

using namespace std;
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vpi = vector<pi>;

int n, m, p, timer = 0, cid = 0;
vvi G; vi X, Y, tin, low, vis, cmp;
vpi pairs;

void dfs(int u, int p) {
    tin[u] = timer++;
    vis[u]++;

    for (auto e : G[u]) {
        int v = X[e] == u ? Y[e] : X[e];
        if (v == p || v == u) continue;
        if (vis[v]) {
            low[u] = min(low[u], tin[v]);
            continue;
        }

        dfs(v, u);
        low[u] = min(low[u], low[v]);
    }
}

const int maxlog = 18;
int tree_timer = 0;
vi tree_tin, tree_tout, par_edge, depth;
vvi up, adj;

void assign(int u, int id) {
    cmp[u] = id;

    for (auto e : G[u]) {
        int v = X[e] == u ? Y[e] : X[e];
        if ((tin[u] < tin[v] && low[v] > tin[u]) || (tin[v] < tin[u] && low[u] > tin[v])) {
            if (cmp[u] != -1 && cmp[v] != -1) {
                adj[cmp[u]].push_back(e);
                adj[cmp[v]].push_back(e);
            }
            continue;
        }
        if (cmp[v] != -1) continue;

        assign(v, id);
    }
}

void dfs2(int u, int p) {
    tree_tin[u] = tree_timer++;
    up[u][0] = p; depth[u] = depth[p] + 1;
    for (int i = 1; i < maxlog; i++) up[u][i] = up[up[u][i-1]][i-1];

    for (auto e : adj[u]) {
        int a = cmp[X[e]], b = cmp[Y[e]];
        int v = a == u ? b : a;

        if (v == p) continue;
        par_edge[v] = e;
        dfs2(v, u);
    }

    tree_tout[u] = tree_timer;
}

bool is_ancestor(int u, int v) {
    return tree_tin[u] <= tree_tin[v] && tree_tout[u] >= tree_tout[v];
}

int lca(int u, int v) {
    if (is_ancestor(u, v)) return u;
    if (is_ancestor(v, u)) return v;

    for (int i = maxlog-1; i >= 0; i--) {
        if (!is_ancestor(up[u][i], v)) u = up[u][i];
    }

    return up[u][0];
}

struct DSU {
    int n; vi par;
    DSU(int N = 0) : n(N), par(N) {for (int i = 0; i < n; i++) par[i] = i;}
    int find(int v) {return par[v] == v ? v : par[v] = find(par[v]);}
    void unite(int a, int b) {if (find(a) != find(b)) par[find(b)] = find(a);}
};

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    G.assign(n+1, vi()); X.resize(m); Y.resize(m); 

    for (int i = 0; i < m; i++) {
        cin >> X[i] >> Y[i];
        G[X[i]].push_back(i);
        G[Y[i]].push_back(i);
    }

    cin >> p; pairs.resize(p);
    for (int i = 0; i < p; i++) cin >> pairs[i].first >> pairs[i].second;

    tin.assign(n+1, INT_MIN); low.assign(n+1, INT_MAX); 
    cmp.assign(n+1, -1); vis.assign(n+1, 0);
    for (int i = 1; i <= n; i++) if (!vis[i]) dfs(i, -1);

    tree_tin.assign(n+1, -1); tree_tout.assign(n+1, -1); par_edge.assign(n+1, -1); depth.assign(n+1, -1);
    adj.resize(n+1); up.assign(n+1, vi(maxlog, -1)); 
    for (int i = 1; i <= n; i++) if (cmp[i] == -1) assign(i, cid++);
    for (int i = 1; i <= n; i++) if (tree_tin[cmp[i]] == -1) dfs2(cmp[i], cmp[i]);

    string ans(m, 'B');
    auto dsu = DSU(n+1);
    for (auto &[u, v] : pairs) {
        int x = cmp[u], y = cmp[v];
        if (x == y) continue;

        int A = lca(x, y);
        x = dsu.find(x); y = dsu.find(y);
        while (depth[x] > depth[A]) {
            bool left = cmp[X[par_edge[x]]] == x;
            int p = left ? cmp[Y[par_edge[x]]] : cmp[X[par_edge[x]]];
            ans[par_edge[x]] = !left ? 'L' : 'R';
            // dsu.unite(p, x);
            // x = dsu.find(x);
            x = p;
        }

        while (depth[y] > depth[A]) {
            bool left = cmp[X[par_edge[y]]] == y;
            int p = left ? cmp[Y[par_edge[y]]] : cmp[X[par_edge[y]]];
            ans[par_edge[y]] = left ? 'L' : 'R';
            // dsu.unite(p, y);
            // y = dsu.find(y);
            y = p;
        }
    }
    cout << ans << "\n";
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...