Submission #1370562

#TimeUsernameProblemLanguageResultExecution timeMemory
1370562fauntleroyOne-Way Streets (CEOI17_oneway)C++20
100 / 100
102 ms29108 KiB
#include <bits/stdc++.h>
using namespace std;

const int n = 100005;

vector<pair<int,int>> g[n]; 
int tin[n], low[n], timer;
bool bridge[n];
bool vis[n];
int d[n];

int comp[n], compcnt;
vector<pair<int,int>> tree[n]; 

vector<pair<int,int>> egs;

void dfs_bridge(int u, int p = -1) {
    vis[u] = true;
    tin[u] = low[u] = ++timer;

    for (auto& [v, id] : g[u]) {
        if (id == p) {
            continue;
        }
        if (vis[v]) {
            low[u] = min(low[u], tin[v]);
        } 
        else {
            dfs_bridge(v, id);
            low[u] = min(low[u], low[v]);

            if (low[v] > tin[u]) {
                bridge[id] = true;
            }
        }
    }
}

void dfs_comp(int u, int c) {
    comp[u] = c;

    for (auto [v, id] : g[u]) {
        if (comp[v] != 0) {
            continue;
        }
        if (bridge[id]) {
            continue;
        }

        dfs_comp(v, c);
    }
}

int up[n][20];

void dfs_lca(int u, int p) {
    up[u][0] = p;

    for (int j = 1; j < 20; j++) {
        up[u][j] = up[up[u][j - 1]][j - 1];
    }
    for (auto [v, id] : tree[u]) {
        if (v == p) {
            continue;
        }
        d[v] = d[u] + 1;
        dfs_lca(v, u);
    }
}

int lift(int v, int k) {
    for (int j = 0; j < 20 ; j++) {
        if (k & (1 << j)) {
            v = up[v][j];
        }
    }
    return v;
}

int lca(int a, int b) {
    if (d[a] < d[b]) {
        swap(a, b);
    }
    a = lift(a, d[a] - d[b]);
    if (a == b) {
        return a;
    }   
    for (int j = 19; j >= 0; j--) {
        if (up[a][j] != up[b][j]) {
            a = up[a][j];
            b = up[b][j];
        }
    }
    return up[a][0];
}

void dfs_sum(int u, int p, vector<int>& cup, vector<int>& cdo, string& ans) {
    for (auto [v, id] : tree[u]) {
        if (v == p) {
            continue;
        }
        dfs_sum(v, u, cup, cdo, ans);
        auto [a, b] = egs[id];
        if (cup[v] > 0) {
            if (comp[a] == v && comp[b] == u) {
                ans[id] = 'R';
            }
            else {
                ans[id] = 'L';
            }
        }

        if (cdo[v] > 0) {
            if (comp[a] == u && comp[b] == v) {
                ans[id] = 'R';
            }
            else {
                ans[id] = 'L';
            }
        }

        cup[u] += cup[v];
        cdo[u] += cdo[v];
    }
}

void solve() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        g[a].push_back({b, i});
        g[b].push_back({a, i});
        egs.push_back({a, b});
    }

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            dfs_bridge(i);
        }
    }

    for (int i = 1; i <= n; i++) {
        if (comp[i] == 0) {
            compcnt++;
            dfs_comp(i, compcnt);
        }
    }

    for (int i = 0; i < m; i++) {
        if (bridge[i]) {
            auto [a, b] = egs[i];
            int ca = comp[a];
            int cb = comp[b];

            tree[ca].push_back({cb, i});
            tree[cb].push_back({ca, i});
        }
    }

    for (int i = 1; i <= compcnt; i++) {
        if (up[i][0] == 0) {
            dfs_lca(i, i);
        }
    }

    vector<int> cup(compcnt + 1);
    vector<int> cdo(compcnt + 1);
    string ans(m, 'B');

    int p;
    cin >> p;

    for (int i = 0; i < p; i++) {
        int x, y;
        cin >> x >> y;
        x = comp[x];
        y = comp[y];
        int z = lca(x, y);
        cup[x]++;
        cup[z]--;
        cdo[y]++;
        cdo[z]--;
    }

    for (int i = 1; i <= compcnt; i++) {
        if (up[i][0] == i) {
            dfs_sum(i, 0, cup, cdo, ans);
        }
    }

    cout << ans << '\n';
}

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

    solve();

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