제출 #1003760

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1003760		coolboy19521	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	162 ms	61188 KiB

oneway

#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
#define int long long

using namespace std;

const int sz = 2e5 + 10;
const int sm = 25;

vector<pair<int, int>> aj[sz], ajgr[sz];
int br[sz], gr[sz], dp[sz];
int in[sz], lo[sz];
int pn[sz], pe[sz];
int le[sz], ri[sz];
int up[sm][sz];
int n, m, p;
bool dr[sz];
char la[sz];
int tr;

void taj(int v, int p = 0) {
    in[v] = lo[v] = ++tr;
    bool ps = false;
    for (auto& u : aj[v]) {
        int to = u.first, nm = u.second;
        if (to == p && !ps) {
            ps = true;
            continue;
        } else if (in[to]) {
            lo[v] = min(lo[v], in[to]);
        } else {
            taj(to, v);
            lo[v] = min(lo[v], lo[to]);
            if (lo[to] > in[v]) {
                br[nm] = true;
            }
        }
    }
}

void cmp(int v, int gn) {
    gr[v] = gn;
    for (auto& u : aj[v]) {
        int to = u.first, nm = u.second;
        if (!gr[to] && !br[nm]) {
            cmp(to, gn);
        }
    }
}

void dpt(int v, int p = 0, int d = 1) {
    up[0][v] = pn[v];
    dp[v] = d;
    for (auto& u : ajgr[v]) {
        int to = u.first, nm = u.second;
        if (to != p) {
            pn[to] = v;
            pe[to] = nm;
            dpt(to, v, d + 1);
        }
    }
}

int lca(int a, int b) {
    if (dp[a] > dp[b]) {
        swap(a, b);
    }
    int d = dp[b] - dp[a];
    for (int i = 0; i < sm; i++) {
        if (d & (1ll << i)) {
            b = up[i][b];
        }
    }
    if (a == b) {
        return a;
    }
    for (int i = sm - 1; i >= 0; i--) {
        if (up[i][a] != up[i][b]) {
            a = up[i][a];
            b = up[i][b];
        }
    }
    return up[0][a];
}

void gdr(int a, int b, int d) {
    if (a == b) {
        return;
    }
    if (!dr[a]) {
        dr[a] = true;
        int to = pn[a];
        int nm = pe[a];
        int gna = gr[le[nm]];
        if (0 == d) {
            if (gna == a) {
                la[nm] = 'R';
            } else {
                la[nm] = 'L';
            }
        } else {
            if (gna == a) {
                la[nm] = 'L';
            } else {
                la[nm] = 'R';
            }
        }
        gdr(to, b, d);
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> n >> m;

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

        aj[a].emplace_back(b, i);
        aj[b].emplace_back(a, i);
        le[i] = a;
        ri[i] = b;
        la[i] = 'B';
    }

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

    int gn = 0;

    for (int i = 1; i <= n; i++) {
        if (!gr[i]) {
            cmp(i, ++gn);
        }
    }

    for (int i = 1; i <= m; i++) {
        if (br[i]) {
            int gna = gr[le[i]];
            int gnb = gr[ri[i]];
            ajgr[gna].emplace_back(gnb, i);
            ajgr[gnb].emplace_back(gna, i);
        }
    }

    for (int i = 1; i <= gn; i++) {
        if (!dp[i]) {
            dpt(i);
        }
    }

    for (int i = 1; i < sm; i++) {
        for (int j = 1; j <= gn; j++) {
            up[i][j] = up[i - 1][up[i - 1][j]];
        }
    }

    vector<vector<int>> ord;

    int q;
    cin >> q;

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

        a = gr[a];
        b = gr[b];
        int l = lca(a, b);
        ord.push_back({dp[l], a, b, l});
    }

    sort(begin(ord), end(ord));

    for (auto& i : ord) {
        int a = i[1];
        int b = i[2];
        int l = i[3];
        gdr(a, l, 0);
        gdr(b, l, 1);
    }

    for (int i = 1; i <= m; i++) {
        cout << la[i];
    }

    cout << '\n';
}

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