제출 #1332220

#제출 시각아이디문제언어결과실행 시간메모리
1332220algoproclubOne-Way Streets (CEOI17_oneway)C++20
100 / 100
103 ms27364 KiB
// UUID: 87f0590f-2adb-4d8e-a5e6-abe9fc499a8a
#include <bits/stdc++.h>

using namespace std;

const int N = 100005, L = 18;
struct Edge { int to, id; };
vector<Edge> g[N], tg[N];
int n, m, k, a[N], b[N], dfn[N], low[N], ti, c[N], cc;
int par[N][L], dep[N], up[N], dn[N];
bool br[N];
char ans[N];

void dfs1(int u, int pid) {
    dfn[u] = low[u] = ++ti;
    for (auto& e : g[u]) {
        if (e.id == pid) continue;
        if (dfn[e.to]) low[u] = min(low[u], dfn[e.to]);
        else {
            dfs1(e.to, e.id);
            low[u] = min(low[u], low[e.to]);
            if (low[e.to] > dfn[u]) br[e.id] = true;
        }
    }
}

void dfs2(int u, int id) {
    c[u] = id;
    for (auto& e : g[u]) 
        if (!c[e.to] && !br[e.id]) dfs2(e.to, id);
}

void dfs3(int u, int p, int d) {
    dep[u] = d; par[u][0] = p;
    for (int i = 1; i < L; i++) par[u][i] = par[par[u][i-1]][i-1];
    for (auto& e : tg[u]) if (e.to != p) dfs3(e.to, u, d + 1);
}

int get_lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = L-1; i >= 0; i--) 
        if (dep[u] - (1 << i) >= dep[v]) u = par[u][i];
    if (u == v) return u;
    for (int i = L-1; i >= 0; i--)
        if (par[u][i] != par[v][i]) u = par[u][i], v = par[v][i];
    return par[u][0];
}

void dfs4(int u, int p) {
    for (auto& e : tg[u]) {
        if (e.to == p) continue;
        dfs4(e.to, u);
        if (up[e.to] > 0) ans[e.id] = (c[a[e.id]] == e.to ? 'R' : 'L');
        else if (dn[e.to] > 0) ans[e.id] = (c[a[e.id]] == u ? 'R' : 'L');
        else ans[e.id] = 'B';
        up[u] += up[e.to]; dn[u] += dn[e.to];
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i];
        g[a[i]].push_back({b[i], i});
        g[b[i]].push_back({a[i], i});
    }
    for (int i = 1; i <= n; i++) if (!dfn[i]) dfs1(i, -1);
    for (int i = 1; i <= n; i++) if (!c[i]) dfs2(i, ++cc);
    for (int i = 1; i <= m; i++) {
        if (br[i]) {
            tg[c[a[i]]].push_back({c[b[i]], i});
            tg[c[b[i]]].push_back({c[a[i]], i});
        } else ans[i] = 'B';
    }
    for (int i = 1; i <= cc; i++) if (!dep[i]) dfs3(i, i, 1);
    cin >> k;
    while (k--) {
        int u, v; cin >> u >> v;
        u = c[u], v = c[v];
        if (u == v) continue;
        int l = get_lca(u, v);
        up[u]++; up[l]--; dn[v]++; dn[l]--;
    }
    for (int i = 1; i <= cc; i++) if (dep[i] == 1) dfs4(i, i);
    for (int i = 1; i <= m; i++) cout << ans[i];
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...