제출 #838107

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
838107		yeediot	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	3 ms	5844 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];
vector<int>nw[mxn];
int val[mxn];
int d[mxn];
struct edge{
    int v,u;
};
vector<edge>e;
bitset<mxn>vis;
int lv[mxn],low[mxn];
int timer=0;
stack<int>st;
vvi bcc;
vector<int>group(mxn);
void tarjan(int v,int pa=-1){
    lv[v]=low[v]=++timer;
    st.push(v);
    for(auto u:adj[v]){
        if(u==pa){
            pa=-1;
            continue;
        }
        if(lv[u]){
            chmin(low[v],lv[u]);
        }
        else{
            tarjan(u,v);
            chmin(low[v],low[u]);
        }
    }
    if(lv[v]==low[v]){
        bcc.pb({});
        while(st.top()!=v){
            bcc.back().pb(st.top());
            group[st.top()]=sz(bcc)-1;
            st.pop();
        }
        bcc.back().pb(st.top());
        group[st.top()]=sz(bcc)-1;
        st.pop();
    }
}
void dfs2(int v,int pa=0){
    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=1;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(!lv[i])tarjan(i);
    }
    for(int i=1;i<=m;i++){
        int a=e[i].v;
        int b=e[i].u;
        int x=group[a];
        int y=group[b];
        if(x!=y){
            nw[x].pb(y);
            nw[y].pb(x);
        }
    }
    int q;
    cin>>q;
    while(q--){
        int a,b;
        cin>>a>>b;
        val[group[a]]++;
        val[group[b]]--;
    }
    for(int i=0;i<sz(bcc);i++){
        if(!d[i])dfs2(i);
    }
    for(int i=0;i<m;i++){
        int x=group[e[i].v];
        int y=group[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: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40