oj.uz

Submission #1105549

# Submission time Handle Problem Language Result Execution time Memory
1105549 2024-10-26T17:21:47 Z asli_bg One-Way Streets (CEOI17_oneway) C++11
0 / 100
 7 ms 19536 KB 
#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], p[MAXN], comp[MAXN];
bool vis[MAXN], isbridge[MAXN];

map<pii,int> ind;

vii edge;

int say;

set<int> out[MAXN], in[MAXN];
vii g[MAXN];
vector<char> ans;

set<pii> tut;

void dfs(int nd,int ata,int h){
    dep[nd]=h;
    low[nd]=h;
    p[nd]=ata;
    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){ //componentlere ayir
    comp[nd]=say;
    for(auto kom:adj[nd]){
        if(kom==p[nd]) continue;
        if(vis[kom]) continue;
        if(isbridge[ind[{nd,kom}]]) continue;
        vis[kom]=true;
        dfs2(kom);
    }
}

void merge(set<int>& a, set<int>& b){
    if(a.size()<b.size()) swap(a,b);
    for(auto el:b) a.insert(el);
}

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];
    }

    //cout<<"here" sp nd sp ata sp ind sp top[nd]<<endl;

    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;

    set<pii> temp;

    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;
        
        say++;
        
        tane[ind[{a,b}]]++;
        temp.insert({a,b});
    }

    FORE(i,1,n+1){
        if(!vis[i]){
            vis[i]=true;
            dfs(i,0,0);
        }
    } 

    memset(vis,0,sizeof vis);

    //contp(edge);

    say=1;
    FORE(i,1,n+1){
        if(!vis[i]){
            vis[i]=true;
            dfs2(i);
            say++;
        }
    }  

    for(auto el:temp){
        tut.insert({comp[el.fi],comp[el.se]});
    }

    //FORE(i,1,n+1) cout<<comp[i]<<' ';
    //cout<<endl;

    //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);

    FORE(i,1,say){
        if(!vis[i]){
            vis[i]=true;
            dfs3(i,0,0);
        }
    }

    FORE(i,1,m+1) cout<<ans[i];
    cout<<endl;
}

//componentlere ayir
//a componentinden b componentine giden bridge i bul

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19280 KB Output is correct
2 Correct 4 ms 19244 KB Output is correct
3 Correct 5 ms 19536 KB Output is correct
4 Correct 7 ms 19536 KB Output is correct
5 Correct 6 ms 19536 KB Output is correct
6 Correct 5 ms 19280 KB Output is correct
7 Correct 6 ms 19536 KB Output is correct
8 Correct 6 ms 19536 KB Output is correct
9 Correct 6 ms 19280 KB Output is correct
10 Incorrect 5 ms 19280 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19280 KB Output is correct
2 Correct 4 ms 19244 KB Output is correct
3 Correct 5 ms 19536 KB Output is correct
4 Correct 7 ms 19536 KB Output is correct
5 Correct 6 ms 19536 KB Output is correct
6 Correct 5 ms 19280 KB Output is correct
7 Correct 6 ms 19536 KB Output is correct
8 Correct 6 ms 19536 KB Output is correct
9 Correct 6 ms 19280 KB Output is correct
10 Incorrect 5 ms 19280 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19280 KB Output is correct
2 Correct 4 ms 19244 KB Output is correct
3 Correct 5 ms 19536 KB Output is correct
4 Correct 7 ms 19536 KB Output is correct
5 Correct 6 ms 19536 KB Output is correct
6 Correct 5 ms 19280 KB Output is correct
7 Correct 6 ms 19536 KB Output is correct
8 Correct 6 ms 19536 KB Output is correct
9 Correct 6 ms 19280 KB Output is correct
10 Incorrect 5 ms 19280 KB Output isn't correct
11 Halted 0 ms 0 KB -