제출 #1333628

#제출 시각아이디문제언어결과실행 시간메모리
1333628azul_safiroOne-Way Streets (CEOI17_oneway)C++20
0 / 100
3090 ms344 KiB
#include <bits/stdc++.h>
// #define int long long
using namespace std;
#define tiii tuple <int, int, int>
#define pii pair <int, int>
int const N = 1e5 + 9, z = 0, R = 1e9 + 7;
vector <vector <pii> > gr;
vector <int> tin;
vector <int> low;
vector <bool> isb;
int timer;

void dfs(int i, int pid) {
    timer ++;
    tin[i] = low[i] = timer;

    for (auto [j, id] : gr[i]) {
        if (id == pid) continue;
        if (!tin[j]) {
            dfs(j, id);
            low[i] = min(low[i], low[j]);

            if (low[j] > tin[i]) isb[id] = true;
        } else {
            low[i] = min(low[i], tin[j]);
        }
    }

    return ;
}

int c = 1;
void dfs1(int i) {
    tin[i] = c;
    for (auto [j, id] : gr[i]) {
        if (tin[j] || isb[id]) continue;
        dfs1(j);
    }

    return ;
}

vector <vector <pii> > g;
vector <int> p, de, pid;
void dfs2(int i) {
    for (auto [j, id] : g[i]) {
        if (j == p[i]) continue;
        de[j] = de[i] + 1;
        p[j] = i;
        pid[j] = id;
        dfs2(j);
    }

    return ;
}

int bl[N][18];
void build(int n) {
    for (int i = 1; i <= n; i ++) bl[i][0] = p[i];
    for (int j = 1; j < 18; j ++) {
        for (int i = 1; i <= n; i ++) {
            bl[i][j] = bl[bl[i][j - 1]][j - 1];
        }
    }

    return ;
}

int lift(int i, int k) {
    for (int j = 0; j < 18; j ++) {
        if (k & (1 << j)) i = bl[i][j];
    }
    return i;
}

int lca(int a, int b) {
    if (de[a] > de[b]) swap(a, b);
    b = lift(b, de[b] - de[a]);

    while (a != b) {
        if (bl[a][0] == bl[b][0]) {
            a = bl[a][0];
            b = bl[b][0];
        } else {
            int l = 0, r = 17;
            while (r - l > 1) {
                int m = (l + r) / 2;
                if (bl[a][m] == bl[b][m]) r = m;
                else l = m;
            }
        }
    }

    return a;
}

void solve() {
    int n, m, q;
    cin >> n >> m;
    gr.assign(n + 1, vector <pii> ());
    tin.assign(n + 1, 0);
    low.assign(n + 1, 0);
    isb.assign(m + 1, false);

    vector <pii> ed(m + 1);

    for (int i = 0; i < m; i ++) {
        int u, v;
        cin >> u >> v;
        gr[u].push_back({v, i + 1});
        gr[v].push_back({u, i + 1});
        ed[i + 1] = {u, v};
    }

    timer = 0;
    for (int i = 1; i <= n; i ++) if (!tin[i]) dfs(i, -1);

    tin.assign(n + 1, 0);
    for (int i = 1; i <= n; i ++) if (!tin[i]) dfs1(i), c ++;

    g.assign(c, vector <pii> ());
    for (int i = 1; i <= n; i ++) {
        for (auto[j, id] : gr[i]) {
            if (!isb[id]) continue;
            g[tin[i]].push_back({tin[j], id});
        }
    }

    n = c - 1;

    p.assign(n + 1, 0);
    pid.assign(n + 1, 0);
    de.assign(n + 1, 0);
    for (int i = 1; i <= n; i ++) if (!p[i]) p[i] = i, dfs2(i);

    build(n);

    vector <int> pi(n + 1);
    vector <int> ans(m + 1, 0);
    for (int i = 1; i <= n; i ++) pi[i] = i;

    cin >> q;
    while (q --) {
        int a, b;
        cin >> a >> b;

        a = tin[a];
        b = tin[b];

        int c = lca(a, b);

        vector <int> vis;
        while (de[a] > de[c]) {
            vis.push_back(a);
            if (pi[a] == a) {
                if (tin[ed[pid[a]].first] == a) ans[pid[a]] = 1;
                else ans[pid[a]] = 2; 
                a = p[a];
            } else {
                a = pi[a];
            }
        }
        for (auto j : vis) pi[j] = a;

        vis.resize(0);
        while (de[b] > de[c]) {
            vis.push_back(b);
            if (pi[b] == b) {
                if (tin[ed[pid[b]].first] == b) ans[pid[b]] = 2;
                else ans[pid[b]] = 1; 
                b = p[b];
            } else {
                b = pi[b];
            }
        }
        for (auto j : vis) pi[j] = b;
    }

    for (int i = 1; i <= m; i ++) {
        if (ans[i] == 0) cout << "B";
        else if (ans[i] == 1) cout << "R";
        else cout << "L";
    }

    cout << '\n';
    return ;
}

signed main() {
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    // cin >> t;

    while (t --) solve();

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