제출 #986322

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

oneway

//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

int n , m , q;
vector<arr(2)> es;
vector<int> g[100000] , tr[100000];
int tin[100000] , low[100000] , emd[100000];
bool ms[100000];
int dsu[100000] , tms[100000][2] , dir[100000];

int findDsu(int v){
    if(dsu[v] == -1) return v;
    return (dsu[v] = findDsu(dsu[v]));
}
void uDsu(int a , int b){
    a = findDsu(a) , b = findDsu(b);
    if(b < a) swap(a , b);
    if(a != b) dsu[b] = a;
}
int timer = 0;
void tarjan(int v = 0 , int p = -1){
    ms[v] = 1 , tin[v] = timer++ , low[v] = tin[v];
    for(int e : g[v]){
        if(e == p) continue;
        int u = es[e][0] + es[e][1] - v;
        if(ms[u]) low[v] = min(low[v] , tin[u]);
        else{
            tarjan(u , e) , low[v] = min(low[v] , low[u]);
            if(low[u] > tin[v]) emd[e] = 1;
        }
    }
}
void dfs1(int v = 0 , int p = -1){
    if(v == 0) timer = -1;
    tms[v][0] = ++timer , ms[v] = 1;
    for(int u : tr[v]){
        if(u == p) continue;
        dfs1(u , v);
    }
    tms[v][1] = timer;
}
void f1(){
    fill(&dsu[0] , &dsu[n] , -1);
    for(int i = 0 ; i < n ; i++) if(!ms[i]) tarjan(i , -1);
    for(int e = 0 ; e < m ; e++){
        if(emd[e] == 1) continue;
        uDsu(es[e][0] , es[e][1]);
    }
    for(int e = 0 ; e < m ; e++){
        if(emd[e] == 1){
            int v = findDsu(es[e][0]) , u = findDsu(es[e][1]);
            tr[v].pb(u) , tr[u].pb(v);
        }
    }
    fill(&ms[0] , &ms[n] , 0);
    for(int i = 0 ; i < n ; i++) if(findDsu(i) == i and !ms[i]) dfs1(i , -1);
}
void dfs2(int v = 0 , int p = -1){
    ms[v] = 1;
    for(int u : tr[v]){
        if(u == p) continue;
        dfs2(u , v) , dir[v] += dir[u];
    }
}

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

    cin >> n >> m;
    for(int i = 0 ; i < m ; i++){
        int v , u;
        cin >> v >> u;
        v-- , u--;
        es.pb({v , u}) , g[v].pb(i) , g[u].pb(i);
    }
    f1();
    cin >> q;
    for(int i = 0 ; i < q ; i++){
        int v , u;
        cin >> v >> u;
        v-- , u--;
        v = findDsu(v) , u = findDsu(u);
        dir[v]++ , dir[u]--;
    }
    fill(&ms[0] , &ms[n] , 0);
    for(int i = 0 ; i < n ; i++) if(findDsu(i) == i and !ms[i]) dfs2(i , -1);
    for(int e = 0 ; e < m ; e++){
        if(emd[e] == 0) cout << 'B';
        else{
            int v = findDsu(es[e][0]) , u = findDsu(es[e][1]);
            if(tms[v][0] < tms[u][0]){
                if(dir[u] == 0) cout << 'B';
                else if(dir[u] < 0) cout << 'R';
                else cout << 'L';
            }else{
                if(dir[v] == 0) cout << 'B';
                else if(dir[v] < 0) cout << 'L';
                else cout << 'R';
            }
        }
    }
}

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