제출 #1282360

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

oneway

#include<bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize("O3,unroll-loops")

const int maxn=1e5;
int n,m;
vector<pair<int,int> >adj[maxn+2];
int dsu[maxn+2],val[maxn+2],vis[maxn+2];
int bridge[maxn+2],disc[maxn+2],low[maxn+2];
pair<int,int>road[maxn+2];

int fin(int a){
    if(dsu[a]==a)return a;
    return dsu[a]=fin(dsu[a]);
}

void merg(int a,int b){
    a=fin(a); b=fin(b);
    if(a==b)return ;
    dsu[a]=b;
}

void dfs(int cur,int par){
    low[cur]=disc[cur]=disc[par]+1;

    int cnt=0;

    for(auto x : adj[cur]){
        if(x.first==par){
            continue;
        }
        if(disc[x.first]){
            low[cur]=min(low[cur],disc[x.first]);
        }
        else{
            dfs(x.first,cur);
            if(low[x.first]>disc[cur]){
                bridge[x.second]=true;
            }
            low[cur]=min(low[cur],low[x.first]);
        }
    }
}

void dfs2(int cur,int par){
    vis[cur]=true;
    for(auto x : adj[cur]){
        if(x.first==par)continue;
        dfs2(x.first,cur);
        val[cur]+=val[x.first];

        if(val[x.first]>0){
            if(road[x.second].first==cur){
                bridge[x.second]=2;
            }
            else{
                bridge[x.second]=1;
            }
        }
        else if(val[x.first]<0){
            if(road[x.second].first==cur){
                bridge[x.second]=1;
            }
            else{
                bridge[x.second]=2;
            }
        }
        else{
            bridge[x.second]=0;
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int q=1;q<=n;q++){
        dsu[q]=q;
    }
    for(int q=1;q<=m;q++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back({v,q});
        adj[v].push_back({u,q});
        road[q]={u,v};
    }

    for(int q=1;q<=n;q++){
        if(disc[q])continue;
        dfs(q,0);
    }
    

    for(int q=1;q<=m;q++){
        if(!bridge[q])merg(road[q].first,road[q].second);
    }
    for(int q=1;q<=n;q++)adj[q].clear();
    for(int q=1;q<=m;q++){
        if(bridge[q]){
            adj[fin(road[q].first)].push_back({fin(road[q].second),q});
            adj[fin(road[q].second)].push_back({fin(road[q].first),q});
        }
    }

    int qu;
    cin>>qu;
    while(qu--){
        int u,v;
        cin>>u>>v;
        val[fin(u)]++; val[fin(v)]--;
    }

    for(int q=1;q<=n;q++){
        if(fin(q)!=q || vis[q])continue;
        dfs2(q,0);
    }
    
    for(int q=1;q<=m;q++){
        if(bridge[q]==0){
            cout<<'B';
        }
        else if(bridge[q]==1){
            cout<<'R';
        }
        else{
            cout<<'L';
        }
    }
    cout<<endl;
}

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