제출 #1331005

#제출 시각아이디문제언어결과실행 시간메모리
1331005algoproclubOne-Way Streets (CEOI17_oneway)C++20
0 / 100
0 ms344 KiB
// UUID: e0da10c9-2a36-41db-a46c-b35b736a2133
#include <bits/stdc++.h>
using namespace std;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pb push_back
#define fst first
#define snd second

template <typename t>
using vv = vector<t>;
template <typename a, typename b>
using pp = pair<a, b>;

typedef long long ll;
typedef double db;

const int mod = 1e9 + 7;

string ans;
vv<vv<pp<int, int>>> edges;
vv<pp<int, int>> par;
vv<int> lev, l, vis, g;
vv<vv<int>> lft;

void sloth(int node) {
    l[node] = lev[node];
    lft[node][0] = par[node].fst;
    for (int i = 1; i < 20; i++) lft[node][i] = lft[lft[node][i - 1]][i - 1];
    vis[node] = 1;
    for (auto [x, id] : edges[node]) {
        if (id == par[node].snd || vis[x] == 2) continue;
        if (!vis[x]) {
            lev[x] = lev[node] + 1;
            par[x] = {node, id};
            sloth(x);
            l[node] = min(l[node], l[x]);
        }
        else l[node] = min(l[node], lev[x]);
    }
    vis[node] = 2;
}

void dfs(int node) {
    if (l[node] == lev[node]) g[node] = node;
    if (node) par[node].fst = g[par[node].fst];
    for (auto [x, id] : edges[node]) {
        if (id != par[x].snd) continue;
        dfs(x);
    }
}

int lca(int u, int v) {
    if (lev[u] < lev[v]) swap(u, v);
    int diff = lev[u] - lev[v];
    for (int i = 0; i < 20; i++) {
        if ((1 << i) & diff) u = lft[u][i];
    }
    if (u == v) return u;
    for (int i = 19; i >= 0; i--) {
        if (lft[u][i] != lft[v][i]) {
            u = lft[u][i];
            v = lft[v][i];
        }
    }
    return lft[u][0];
}

void add(int u, int v, char c) {
    while (lev[u] > lev[v]) {
        ans[par[u].snd] = c;
        int nxt = par[u].fst;
        par[u].fst = v;
        u = nxt;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, m, q;
    cin >> n >> m;
    ans.assign(m, 'B');
    edges.resize(n);
    par.resize(n);
    lev.resize(n);
    l.resize(n);
    vis.assign(n, 0);
    g.resize(n);
    lft.assign(n, vv<int>(20, 0));
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        edges[u].pb({v, i});
        edges[v].pb({u, i});
    }
    for (int i = 0; i < n; i++) {
        if (vis[i]) continue;
        lev[i] = 0;
        par[i] = {i, -1};
        sloth(i);
        dfs(i);
    }
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        u = g[u]; v = g[v];
        int mid = g[lca(u, v)];
        add(u, mid, 'R');
        add(v, mid, 'L');
    }
    cout << ans;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...