Submission #838090

#	Time	Username	Problem	Language	Result	Execution time	Memory
838090		yeediot	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	10 ms	11636 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<pii>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);
vector<bool>bridge(mxn);
void tarjan(int v,int pa,int id=-1){
    vis[v]=1;
    lv[v]=low[v]=++timer;
    st.push(v);
    for(auto [u,idx]:adj[v]){
        if(idx==id)continue;
        if(vis[u]){
            chmin(low[v],lv[u]);
        }
        else{
            tarjan(u,v,idx);
            chmin(low[v],low[u]);
        }
    }
    if(lv[v]==low[v]){
        bridge[id]=1;
        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){
    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,i});
        adj[b].pb({a,i});
    }
    tarjan(1,1);
    for(int i=1;i<=m;i++){
        int a=e[i].v;
        int b=e[i].u;
        if(bridge[i]){
            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<sz(bcc);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";
            }
        }
    }cout<<'\n';
}
 /*
 input:
 
 */

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