Submission #838131

#TimeUsernameProblemLanguageResultExecution timeMemory
838131yeediotOne-Way Streets (CEOI17_oneway)C++17
100 / 100
70 ms23324 KiB
#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;
int bccnt=0;
vector<int>group(mxn);
vector<bool>bridge(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]){
            tarjan(u,v);
            chmin(low[v],low[u]);
        }
        else{
            chmin(low[v],lv[u]);
        }
    }
    if(lv[v]==low[v]){
        while(st.top()!=v){
            group[st.top()]=bccnt;
            st.pop();
        }
        group[st.top()]=bccnt;
        st.pop();
        bccnt++;
    }
}
void dfs2(int v,int pa=0){
    d[v]=d[pa]+1;
    vis[v]=1;
    for(auto u:nw[v]){
        if(vis[u])continue;
        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(!vis[i])tarjan(i,i);
    }
    for(int i=0;i<m;i++){
        int a=e[i].v;
        int b=e[i].u;
        if(group[a]!=group[b]){
            int x=group[a];
            int y=group[b];
            nw[x].pb(y);
            nw[y].pb(x);
        }
    }
    vector<char>ans(m+1,'B');
    int q;
    cin>>q;
    while(q--){
        int a,b;
        cin>>a>>b;
        val[group[a]]++;
        val[group[b]]--;
    }
    vis.reset();
    for(int i=0;i<bccnt;i++){
        if(!vis[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";
            }
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...