Submission #1131233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131233		aram.hosna	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	16 ms	21568 KiB

oneway

/* KHODA HAST */
#include <bits/stdc++.h>

using namespace std;

typedef long long ll ;
typedef pair<ll , ll > pii ;
const ll mod = 1e9 +7;
const ll inf = 8e18;
const int N = 3e5+12 ;

#define s second
#define f first
#define pb push_back
#define ms(x , y) memset(x , y , sizeof x)
#define ret(x) cout << x << endl ,exit(0) ;

ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

vector <pii> adj[N] , adj2[N] ;
vector <int> vh[N] ;
bool bor[N] , sn[N]  ;
int mol[N] , r[N] , l[N] , t = 0 , h[N] , tim = 0 , st[N] , ps[2][N] , y[2][N] , ps1[N] , thes[N];
int n , m ;
void dfs(int v , int p, int y ){
    sn[v] = 1 ;
    for(pii u : adj[v]){
        if(!sn[u.f]){
            h[u.f] = h[v]+1 ;
            dfs(u.f , v , u.s) ;
            ps1[v]+=ps1[u.f] ;
        }
        if(sn[u.f] && u.f != p && h[u.f] < h[v] ){
             ps1[u.f]-- ; ps1[v]++ ;
        }
    }
    if(ps1[v] == 0 && p!=0 ){
        bor[y] = 1 ;
    }
}

void dfs2(int v){
    sn[v] = 1 ; mol[v] = t ;
    for(pii u : adj[v]){
        if(!sn[u.f] && !bor[u.s])dfs2(u.f);
    }
}

void dfs3(int v) {
    sn[v] = 1 ;
    for(pii u : adj[v]){
        if(!sn[u.f]) {
                if(bor[u.s]){
            adj2[mol[u.f]].pb({mol[v] , u.s}) ;
            adj2[mol[v]].pb({mol[u.f] , u.s}) ;
                }
                dfs3(u.f) ;
        }
    }
}
void dfs4(int v){
    sn[v] = 1 ;
    thes[tim] = v ;
    vh[h[v]].pb(tim) ;
    tim++;
    for(pii u : adj2[v]){
        if(!sn[u.f]){
            h[u.f] = h[v]+1 ;
            dfs4(u.f) ;
        }
    }
    tim++;
    return ;
}

void dfs5(int v ){
    sn[v] = 1 ;
    for(pii u : adj2[v]){
        if(!sn[u.f]){
                ps[0][u.f] += ps[0][v] ;
            dfs5(u.f) ;
                ps[1][v] += ps[1][u.f] ;
                y[1][u.s] = u.f ; y[0][u.s] = v ;
        }
    }
    return ;
}

int the_jad(int v , int k ){
    if(vh[h[v] - k ].size() == 0 || h[v] < k )return -1 ;
    auto u = upper_bound(vh[h[v] - k  ].begin() , vh[h[v] - k  ].end() , st[v]) - vh[h[v] - k].begin();
    u = vh[h[v] - k ][u] ;
    return thes[u] ;
}

int lca(int x , int y){
    int l = 0 , r = n+1 , md ;
    while(r - l > 1){
        md = (l+r)/2 ;
        if(the_jad(x , md) == the_jad(y , md) || the_jad(x , md) == -1 || the_jad(y , md) == -1 ){
            r = md ;
        }
        else l = md ;
    }
    return the_jad(x , r) ;
}

void solve(){

    cin >> n >> m ;
    fill(sn , sn+n+ 1 , 0 ) ;
    for(int i = 0 ; i <= n ; i++){
        st[i] = 0 ;
        thes[i] = 0 ;
    }
    for(int i = 1 ; i <= m ; i++){
        int v , u ;
        cin >> v >> u ; adj[u].pb({v , i}); adj[v].pb({u , i});
        r[m] = u , l[m] = v;
    }
    h[1] = 0 ;
    dfs(1 , 0 , 0 ) ;

    fill(sn , sn+n+ 1 , 0 ) ;
    for(int i = 1 ; i <= n ; i++)
            if(!sn[i]){t++; dfs2(i) ; }
    fill(sn , sn+n+ 1 , 0 ) ;
    dfs3(1) ;
    fill(sn , sn+n+1 , 0) ;
    fill(h , h+n+1 , 0 ) ;
    dfs4(1) ;
    int p ;
    cin >> p ;
    while(p--){
        int x , y ;
        cin >> x >> y ;
        x = mol[x] ; y = mol[y] ;
        if(x == y)continue ;
        int p = lca(x , y ) ;
        ps[1][x]++ ; ps[1][p]--;
        ps[0][y]--; ps[0][p]++;
    }
    fill(sn , sn+n+1 , 0) ;
    dfs5(1) ;

    string ans = "" ;
        for(int i = 1 ; i <= m ; i++){
        int up = y[1][i] , dw = y[0][i] ;
        if(bor[i] == 1 ) {
        if(ps[1][up] > 0 ){
            if(r[i] == up )ans+='L' ;
            else ans+='R' ;
        }
       else if(ps[0][dw] > 0){
            if(r[i] == dw )ans+='L' ;
            else ans+='R' ;
        }
        }
        else ans+='B' ;
    }
    cout << ans << endl;
}

int main(){
    cin.tie(0)->sync_with_stdio(0) ;
    solve() ;
    return 0 ;
}

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