제출 #159040

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

oneway

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+5;
int currtime;
int n,m;
int k;
int a[MAXN];
vector<int> v1[MAXN];
int bg[MAXN];
vector<int> v2[MAXN];
int b[MAXN];
int p[MAXN];
int s[MAXN];
int tin[MAXN];
int dist[MAXN];
int low[MAXN];
int sz[MAXN];
int find(int a){
    if(p[a] == a){
        return a;
    }
    return p[a] = find(p[a]);
}
void join(int a,int b){
    a = find(a);
    b = find(b);
    if(a==b){
        return;
    }
    if(sz[a]<sz[b]){
        swap(a,b);
    }
    p[b] = a;
    sz[a] +=sz[b];
}
void dfs(int curr,int par){
    tin[curr] = low[curr] = currtime++;
    for(int x:v1[curr]){
        int next = curr^a[x]^b[x];
        if(!tin[next]){
            dfs(next,x);
            low[curr] = min(low[curr],low[next]);
            if(low[next]>tin[curr]){
                bg[x] = 1;
            }
        }else if(x!=par){
            low[curr]=min(low[curr],tin[next]);
        }
    }
}
void dfs2(int curr,int par){
    for(int x:v2[curr]){
        int next = curr^a[x]^b[x];
        if(next == par){
            continue;
        }
        dist[next] = dist[curr]+1;
        dfs2(next,curr);
        s[curr]+=s[next];
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        p[i] = i;
    }
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i];
        v1[a[i]].push_back(i);
        v1[b[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        if(!tin[i]){
            dfs(i,-1);
        }
    }
    for(int i=1;i<=m;i++){
        if(!bg[i]){
            join(a[i],b[i]);
        }
    }
    for(int i=1;i<=m;i++){
        if(!bg[i]){
            continue;
        }
        a[i]= find(a[i]);
        b[i] = find(b[i]);
        v2[a[i]].push_back(i);
        v2[b[i]].push_back(i);
    }
    cin>>k;
    while(k--){
        int x,y;
        cin>>x>>y;
        s[find(x)]++;
        s[find(y)]--;
    }
    for(int i=1;i<=n;i++){
        if(p[i] == i && !dist[i]){
            dist[i] = 1;
            dfs2(i,-1);
        }

    }
    for(int i=1;i<=m;i++){
        if(!bg[i]){
            cout<<'B';
            continue;
        }
        int node;
        if(dist[a[i]]>dist[b[i]]){
            node = a[i];
        }else{
            node = b[i];
        }
        if(s[node]==0){
            cout<<'B';
            continue;
        }
        if((s[node]>0 && node==a[i])||(s[node]<0 && node==b[i])){
            cout<<'R';
        }else{
            cout<<'L';
        }
    }
}

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