제출 #510576

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
510576		Monarchuwu	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	192 ms	29556 KiB

oneway

#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

typedef pair<int, int> pii;
#define ff first
#define ss second

const int N = 1e5 + 9;
int n, m, p;
int a[N], b[N], x[N], y[N];
vector<int> g[N];

int num[N], low[N], tme;
int stk[N], top;
int lab[N], cnt_scc;
void tarjan(int u, int p) {
    num[u] = low[u] = ++tme;
    stk[++top] = u;
    for (int v : g[u]) {
        if (v == p) {
            p = 0;
            continue;
        }

        if (num[v]) low[u] = min(low[u], num[v]);
        else {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
        }
    }

    if (num[u] == low[u]) { // chot
        lab[u] = ++cnt_scc;
        while (stk[top] != u)
            lab[stk[top--]] = cnt_scc;
        --top;
    }
}

int h[N], par[N][17];
void dfs(int u) {
    sort(all(g[u]));
    for (int v : g[u]) if (v != par[u][0]) {
        h[v] = h[u] + 1;
        par[v][0] = u;
        for (int j = 1; (1 << j) <= h[v]; ++j)
            par[v][j] = par[par[v][j - 1]][j - 1];
        dfs(v);
    }
}
int st[N][17];
void gogo(int u, int v) {
    if (h[u] > h[v]) {
        int k = h[u] - h[v];
        for (int j = log2(k); ~j; --j)
            if (k >> j & 1) {
                st[u][j] |= 1; // u->par
                u = par[u][j];
            }
    }
    if (h[u] < h[v]) {
        int k = h[v] - h[u];
        for (int j = log2(k); ~j; --j)
            if (k >> j & 1) {
                st[v][j] |= 2; // par->v
                v = par[v][j];
            }
    }
    if (u == v) return;

    for (int j = log2(h[u]); ~j; --j)
        if (par[u][j] != par[v][j]) {
            st[u][j] |= 1;
            st[v][j] |= 2;
            u = par[u][j];
            v = par[v][j];
        }
    st[u][0] |= 1;
    st[v][0] |= 2;
}

int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> a[i] >> b[i];
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    cin >> p;
    for (int i = 0; i < p; ++i)
        cin >> x[i] >> y[i];
    for (int i = 1; i <= n; ++i)
        if (!num[i]) tarjan(i, 0);

    for (int i = 1; i <= n; ++i) g[i].clear();
    for (int i = 0; i < m; ++i) if (lab[a[i]] != lab[b[i]]) {
        g[lab[a[i]]].push_back(lab[b[i]]);
        g[lab[b[i]]].push_back(lab[a[i]]);
    }
    fill(h + 1, h + cnt_scc + 1, -1);
    for (int i = 1; i <= cnt_scc; ++i)
        if (h[i] == -1) h[i] = 0, dfs(i);

    for (int i = 0; i < p; ++i) {
        if (lab[x[i]] != lab[y[i]])
            gogo(lab[x[i]], lab[y[i]]);
    }

    for (int j = 16; j; --j)
        for (int i = 1; i <= n; ++i) {
            st[i][j - 1] |= st[i][j];
            st[par[i][j - 1]][j - 1] |= st[i][j];
        }

    for (int i = 0, u, v; i < m; ++i) {
        u = lab[a[i]], v = lab[b[i]];
        if (u == v) cout << 'B';
        else {
            if (par[u][0] == v) {   // u->v
                cout << "BRL"[st[u][0]];
            }
            else {                  // v->u
                cout << "BLR"[st[v][0]];
            }
        }
    }
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40