제출 #1257077

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257077		nikaa123	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	676 ms	327680 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define eb emplace_back
#define mp make_pair
#define pb push_back
#define pp pop_back
#define endl '\n'
#define ff first
#define ss second
#define sz(x) (int)x.size()

typedef pair<int, int> pii;

const int N = 1e5 + 5;
const int M = 2e5 + 5;

int n, m, p, a, b;
int visited[N];
int low[N], inT[N], outT[N];
int timer;
struct Edge { int to, id; };
vector<vector<Edge>> v(N), v1(N);
struct R { int a, b, id; };
vector<R> roads;

int up[N][20];
bool isbridge[M];
char ans[M];

int comp[N];
vector<int> lst;

void dfs1(int x, int p, int peid) {
    visited[x] = true;
    inT[x] = low[x] = timer++;
    for (auto e : v[x]) {
        int to = e.to, eid = e.id;
        if (eid == peid) continue;
        if (visited[to]) {
            low[x] = min(low[x], inT[to]);
        } else {
            dfs1(to, x, eid);
            low[x] = min(low[x], low[to]);
            if (low[to] > inT[x]) {
                isbridge[eid] = true;
                v1[to].pb({x, eid});
                v1[x].pb({to, eid});
            }
        }
    }
}

void dfs2(int x) {
    lst.pb(x);
    visited[x] = true;
    for (auto e : v[x]) {
        int to = e.to, eid = e.id;
        if (visited[to]) continue;
        if (isbridge[eid]) continue;
        dfs2(to);
    }
}

void dfs3(int x, int p) {
    inT[x] = timer++;
    up[x][0] = p;
    visited[x] = true;
    for (int i = 1; i <= 17; i++) {
        up[x][i] = up[up[x][i-1]][i-1];
    }
    for (auto e : v[x]) {
        int to = e.to;
        if (to == p) continue;
        dfs3(to, x);
    }
    outT[x] = timer++;
}

bool ispar(int a, int b) {
    return (inT[a] < inT[b] && outT[a] > outT[b]);
}

int lca(int a, int b) {
    if (ispar(a, b)) return a;
    if (ispar(b, a)) return b;
    for (int i = 17; i >= 0; i--) {
        if (!ispar(up[a][i], b)) {
            a = up[a][i];
        }
    }
    return up[a][0];
}

inline void test_case() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        v[a].pb({b, i});
        v[b].pb({a, i});
        roads.pb({a, b, i});
        ans[i] = 'B';
    }
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) dfs1(i, -1, -1);
    }
    for (int i = 1; i <= n; i++) visited[i] = false;
    int id = n + 1;
    for (int i = 1; i <= n; i++) {
        if (visited[i]) continue;
        lst.clear();
        dfs2(i);
        if (sz(lst) > 1) {
            for (auto x : lst) {
                comp[x] = id;
            }
        }
    }
    for (int i = 1; i <= n; i++) visited[i] = false;
    for (auto r : roads) {
        int a = r.a, b = r.b;
        for (auto e : v[a]) if (e.to == b) {
            if (!isbridge[e.id]) {
                if (comp[a]) {
                    v1[a].pb({comp[a], e.id});
                    v1[comp[a]].pb({a, e.id});
                }
                if (comp[b]) {
                    v1[b].pb({comp[b], e.id});
                    v1[comp[b]].pb({b, e.id});
                }
            }
            break;
        }
    }
    v = v1;
    for (int i = 1; i <= n; i++) visited[i] = false;
    timer = 0;
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) dfs3(i, i);
    }
    cin >> p;
    while (p--) {
        cin >> a >> b;
        int l = lca(a, b);
        while (a != l) {
            int x = up[a][0];
            for (auto e : v[a]) if (e.to == x) {
                if (ans[e.id] == 'B') {
                    ans[e.id] = 'R';
                }
                break;
            }
            a = x;
        }
        while (b != l) {
            int x = up[b][0];
            for (auto e : v[b]) if (e.to == x) {
                if (ans[e.id] == 'B') {
                    ans[e.id] = 'L';
                }
                break;
            }
            b = x;
        }
    }
    for (auto r : roads) cout << ans[r.id];
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    test_case();
    return 0;
}

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