Submission #1106908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106908		asli_bg	One-Way Streets (CEOI17_oneway)	C++11	100 / 100	379 ms	53664 KiB

oneway

#pragma GCC optimize("O3,unroll-loops")
 
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)
 
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<pii> vii;
 
#define cont(x) for(auto el:x) {cout<<el<<' ';} cout<<endl;
#define endl '\n'
#define contp(x) for(auto el:x) {cout<<el.fi<<'-'<<el.se<<' ';} cout<<endl;
#define pb push_back
 
#define sp <<' '<<
 
#define DEBUG(x) {cout<<(#x) sp x<<endl;}
#define carp(x,y) ((x%MOD)*(y%MOD))%MOD
#define topla(x,y) ((x%MOD)+(y%MOD))%MOD
 
const int MAXN=1e5+5;
 
int n,m;
vi adj[MAXN];
int tane[MAXN], dep[MAXN], low[MAXN], comp[MAXN];
bool vis[MAXN], isbridge[MAXN];
 
map<pii,int> ind;

int say;

vii g[MAXN];
vector<char> ans;
 
set<pii> tut;
set<pii> temp;
vii edge;
 
void dfs(int nd,int ata,int h){
    dep[nd]=h;
    low[nd]=h;
    for(auto kom:adj[nd]){
        if(kom==ata) continue;
        if(vis[kom]){
            if(dep[kom]<=dep[nd]){ //back edge
                low[nd]=min(low[nd],dep[kom]);
            }
            continue;
        }
        vis[kom]=true;
        dfs(kom,nd,h+1);
        low[nd]=min(low[nd],low[kom]);
    }
 
    if(ata!=0 and low[nd]>=dep[nd] and tane[ind[{ata,nd}]]<=1){
        isbridge[ind[{ata,nd}]]=true;
        edge.pb({ata,nd});
    }
}
 
void dfs2(int nd,int ata){ //componentlere ayir
    comp[nd]=say;
    for(auto kom:adj[nd]){
        if(kom==ata) continue;
        if(vis[kom]) continue;
        if(isbridge[ind[{nd,kom}]]) continue;
        vis[kom]=true;
        dfs2(kom,nd);
    }
}


int top[MAXN];
void dfs3(int nd,int ata,int ind){
    for(auto el:g[nd]){
        int kom=el.fi;
        int yer=el.se;
        if(kom==ata) continue;
        if(vis[kom]) continue;
        vis[kom]=true;
        dfs3(kom,nd,yer);
        top[nd]+=top[kom];
    }
 
    if(ind==-1) return;
 
    if(top[nd]<0){ //bana edge çek
        if(tut.count({ata,nd})) ans[ind]='R';
        else ans[ind]='L';
    }
    else if(top[nd]>0){ //benden edge çek
        if(tut.count({ata,nd})) ans[ind]='L';
        else ans[ind]='R';
    }
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n>>m;
 
    say=1;
    FOR(i,m){
        int a,b;
        cin>>a>>b;
 
        adj[a].pb(b);
        adj[b].pb(a);
 
        //yeni bir edgese
        if(ind[{a,b}]==0) ind[{a,b}]=ind[{b,a}]=say++;
        else say++;
        tane[ind[{a,b}]]++;
        temp.insert({a,b});
    }
    
    //bridgeleri bul
    FORE(i,1,n+1){
        if(!vis[i]){
            vis[i]=true;
            dfs(i,0,0);
        }
    } 
 
    memset(vis,0,sizeof vis);

    //componentlere ayir
    say=1;
    FORE(i,1,n+1){
        if(!vis[i]){
            vis[i]=true;
            dfs2(i,0);
            say++;
        }
    }  
 
    for(auto el:temp){
        if(comp[el.fi]==comp[el.se]) continue;
        tut.insert({comp[el.fi],comp[el.se]});
    }
 
    //create the condensation graph
    for(auto el:edge){
        g[comp[el.fi]].pb({comp[el.se],ind[el]});
        g[comp[el.se]].pb({comp[el.fi],ind[el]});
    }
 
    int p;
    cin>>p;
    while(p--){
        int a,b;
        cin>>a>>b;
        top[comp[a]]++;
        top[comp[b]]--;
    }
 
    ans.resize(m+1,'B');
 
    memset(vis,0,sizeof vis);
    
    //yönleri belirle
    FORE(i,1,say+1){
        if(!vis[i]){
            vis[i]=true;
            dfs3(i,0,-1);
        }
    }
 
    FORE(i,1,m+1) cout<<ans[i];
    cout<<endl;
}

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