제출 #838122

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

oneway

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
const int mxn=1e5+5;
vector<int>adj[mxn];
unordered_set<int>nw[mxn];
int val[mxn];
int d[mxn];
struct edge{
    int v,u;
};
vector<edge>e;
bitset<mxn>vis;
int dfn[mxn],low[mxn];
int timer=0;
stack<int>st;
int bccnt=0;
bool ins[mxn];
vector<int>id(mxn);
void tarjan(int v,int pa=-1){
    dfn[v]=low[v]=++timer;
    st.push(v);
    ins[v]=1;
    for(auto u:adj[v]){
        if(u==pa){
            pa=-1;
            continue;
        }
        if(!dfn[u]){
            tarjan(u,v);
            chmin(low[v],low[u]);
        }
        else if(ins[u]){
            chmin(low[v],dfn[u]);
        }
    }
    if(dfn[v]==low[v]){
        while(st.top()!=v){
            id[st.top()]=bccnt;
            ins[st.top()]=0;
            st.pop();
        }
        id[st.top()]=bccnt;
        ins[st.top()]=0;
        st.pop();
        bccnt++;
    }
}
void dfs2(int v,int pa=-1){
    for(auto u:nw[v]){
        if(u==pa)continue;
        d[u]=d[v]+1;
        dfs2(u,v);
        val[v]+=val[u];
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        e.pb({a,b});
        adj[a].pb(b);
        adj[b].pb(a);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i,-1);
    }
    for(int i=0;i<m;i++){
        int a=e[i].v;
        int b=e[i].u;
        int x=id[a];
        int y=id[b];
        if(x!=y){
            nw[x].insert(y);
            nw[y].insert(x);
        }
    }
    int q;
    cin>>q;
    while(q--){
        int a,b;
        cin>>a>>b;
        val[id[a]]++;
        val[id[b]]--;
    }
    for(int i=0;i<bccnt;i++){
        if(!d[i])dfs2(i);
    }
    for(int i=0;i<m;i++){
        int x=id[e[i].v];
        int y=id[e[i].u];
        if(x==y){
            cout<<"B";
        }
        else{
            if(d[x]>d[y]){
                if(val[x]==0)cout<<"B";
                else if(val[x]>0)cout<<"R";
                else cout<<"L";
            }
            else{
                if(val[y]==0)cout<<"B";
                else if(val[y]<0)cout<<"R";
                else cout<<"L";
            }
        }
    }
}
 /*
 input:
 
 */

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