제출 #761468

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

oneway

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

typedef long long ll; 

#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)
const int N = 1e5 + 5; 

int n, m, q; 
int U[N], V[N], col, color[N], direction[N], sum[N]; 
bool is_bridge[N]; 
int tin[N], tim, low[N], pa[N]; 
vector <int> adj[N], curr;   
 
void dfs(int u, int f){
    tin[u] = low[u] = ++tim; 
    curr.push_back(u); 
    pa[u] = f; 

    int r = 0;  
    for(int v: adj[u]){
        if(v == f) {r++; continue; } 
        if(tin[v] == 0){
            dfs(v, u); 
            low[u] = min(low[u], low[v]); 
        }
        else low[u] = min(low[u], tin[v]); 
    }
    if(low[u] == tin[u] and r <= 1) {
        col++; 
        while(!curr.empty()){
            int w = curr.back();
            color[w] = col; 
            curr.pop_back(); 
            if(w == u) break; 
        }
        if(f != 0) 
            is_bridge[u] = 1;
    }
}
void DFS(int u, int f){
    tin[u] = ++tim; 
    for(int v: adj[u]){
        if(v == f) continue; 
        if(tin[v] == 0){
            DFS(v, u); 
            sum[u] += sum[v]; 
        }
    }
}
int main(){
    cin >> n >> m; 
    f(i,0,m){
        cin >> U[i] >> V[i]; 
        if(U[i] != V[i]) 
            adj[U[i]].push_back(V[i]), adj[V[i]].push_back(U[i]); 
    }
 
    f(i,1,n+1) if(tin[i] == 0) dfs(i, 0); 
    
    cin >> q; 
    f(i,0,q){
        int u, v; 
        cin >> u >> v; 
        if(color[u] != color[v]) sum[u]++, sum[v]--; 
    }

    tim = 0; 
    f(i,1,n+1) tin[i] = 0; 
    f(i,1,n+1) if(tin[i] == 0) DFS(i, 0); 

    f(i,1,n+1) if(is_bridge[i] and sum[i] != 0) direction[i] = sum[i]/abs(sum[i]); 

    f(i,0,m){
        if((pa[U[i]] == V[i] and direction[U[i]] == 1) or (pa[V[i]] == U[i] and direction[V[i]] == -1)) cout << 'R'; 
        else if((pa[U[i]] == V[i] and direction[U[i]] == -1) or (pa[V[i]] == U[i] and direction[V[i]] == 1)) cout << 'L'; 
        else cout << 'B'; 
    }
    cout << "\n"; 
    return 0; 
}

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