제출 #1149003

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149003		daoquanglinh2007	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	269 ms	51928 KiB

oneway

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

#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 1e5, LOG = 16;

int n, m, a[NM+5], b[NM+5];
vector <pii> adj[NM+5];
int p, u[NM+5], v[NM+5];
map <pii, int> cnt;
int timer = 0, num[NM+5], low[NM+5];
bool is_bridge[NM+5];
int parent[NM+5], sz[NM+5];
vector <int> g[NM+5];
int dep[NM+5], jump[NM+5][LOG+5], dp[NM+5][LOG+5];

void dfs(int u, int p){
    low[u] = num[u] = ++timer;
    for (pii _ : adj[u]){
        int v = _.fi, id = _.se;
        if (v == p) continue;
        if (num[v] > 0){
            low[u] = min(low[u], num[v]);
        }
        else{
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (cnt[mp(u, v)] == 1 && low[v] > num[u]) is_bridge[id] = 1;
        }
    }
}

void make_set(int v){
    parent[v] = v;
    sz[v] = 1;
}

int find_set(int v){
    return parent[v] == v ? v : parent[v] = find_set(parent[v]);
}

void union_sets(int u, int v){
    u = find_set(u);
    v = find_set(v);
    if (u == v) return;
    if (sz[u] < sz[v]) swap(u, v);
    parent[v] = u;
    sz[u] += sz[v];
}

void dfs2(int u, int p){
    dep[u] = (p == -1 ? 0 : dep[p]+1);
    jump[u][0] = p;
    for (int i = 1; i <= LOG; i++)
        if (jump[u][i-1] == -1) jump[u][i] = -1;
        else jump[u][i] = jump[jump[u][i-1]][i-1];

    for (int v : g[u]){
        if (v == p) continue;
        dfs2(v, u);
    }
}

int lca(int u, int v){
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = LOG; i >= 0; i--)
        if (dep[u]-(1<<i) >= dep[v]) u = jump[u][i];
    if (u == v) return u;
    for (int i = LOG; i >= 0; i--)
        if (jump[u][i] != jump[v][i]){
            u = jump[u][i];
            v = jump[v][i];
        }
    return jump[u][0];
}

void update(int u, int p, int val){
    for (int i = LOG; i >= 0; i--)
        if (dep[u]-(1<<i) >= dep[p]){
            dp[u][i] = val;
            u = jump[u][i];
        }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> a[i] >> b[i];
        cnt[mp(a[i], b[i])]++;
        cnt[mp(b[i], a[i])]++;
        if (cnt[mp(a[i], b[i])] > 1) continue;
        adj[a[i]].push_back(mp(b[i], i));
        adj[b[i]].push_back(mp(a[i], i));
    }
    cin >> p;
    for (int i = 1; i <= p; i++)
        cin >> u[i] >> v[i];
    for (int i = 1; i <= n; i++){
        if (!num[i]) dfs(i, -1);
        make_set(i);
    }

    for (int i = 1; i <= m; i++){
        if (!is_bridge[i]) union_sets(a[i], b[i]);
    }
    for (int i = 1; i <= m; i++){
        int u = find_set(a[i]), v = find_set(b[i]);
        if (u != v){
            g[u].push_back(v);
            g[v].push_back(u);
        }
    }

    for (int u = 1; u <= n; u++){
        if (parent[u] != u) continue;
        if (jump[u][0] == 0) dfs2(u, -1);
    }
    for (int i = 1; i <= p; i++){
        int x = find_set(u[i]), y = find_set(v[i]);
        if (x == y) continue;
        int p = lca(x, y);
        update(x, p, 1);
        update(y, p, 2);
    }
    for (int i = LOG; i > 0; i--){
        for (int u = 1; u <= n; u++){
            if (parent[u] != u || dp[u][i] == 0) continue;
            dp[u][i-1] = dp[u][i];
            dp[jump[u][i-1]][i-1] = dp[u][i];
        }
    }
    for (int i = 1; i <= m; i++){
        int u = find_set(a[i]), v = find_set(b[i]);
        if (u == v){
            cout << 'B';
            continue;
        }
        if (dep[u] > dep[v]){
            if (dp[u][0] == 0) cout << 'B';
            else if (dp[u][0] == 1) cout << 'R';
            else cout << 'L';
        }
        else{
            if (dp[v][0] == 0) cout << 'B';
            else if (dp[v][0] == 1) cout << 'L';
            else cout << 'R';
        }
    }
    return 0;
}

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