oj.uz

Submission #1106905

# Submission time Handle Problem Language Result Execution time Memory
1106905 2024-10-31T09:03:04 Z asli_bg One-Way Streets (CEOI17_oneway) C++11
100 / 100
 419 ms 63928 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=2e5+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;
 
vii edge;
 
int say;

vii g[MAXN];
vector<char> ans;
 
set<pii> tut;

set<pii> temp;

 
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;
        if(temp.count({ata,nd})) edge.pb({ata,nd});
        else edge.pb({nd,ata});
    }
}
 
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];
    }
 
    //cout<<"here" sp nd sp ata sp ind sp top[nd]<<endl;
    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});
    }
 
    FORE(i,1,n+1){
        if(!vis[i]){
            vis[i]=true;
            dfs(i,0,0);
        }
    } 
 
    memset(vis,0,sizeof vis);

    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]});
    }
 
    //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+1){
        if(!vis[i]){
            vis[i]=true;
            dfs3(i,0,-1);
        }
    }
 
    FORE(i,1,m+1) cout<<ans[i];
    cout<<endl;
}
 
//componentlere ayir
//a componentinden b componentine giden bridge i bul

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15952 KB Output is correct
2 Correct 6 ms 15952 KB Output is correct
3 Correct 6 ms 16208 KB Output is correct
4 Correct 8 ms 16208 KB Output is correct
5 Correct 7 ms 16464 KB Output is correct
6 Correct 6 ms 16208 KB Output is correct
7 Correct 8 ms 16464 KB Output is correct
8 Correct 7 ms 16380 KB Output is correct
9 Correct 5 ms 16208 KB Output is correct
10 Correct 6 ms 16376 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15952 KB Output is correct
2 Correct 6 ms 15952 KB Output is correct
3 Correct 6 ms 16208 KB Output is correct
4 Correct 8 ms 16208 KB Output is correct
5 Correct 7 ms 16464 KB Output is correct
6 Correct 6 ms 16208 KB Output is correct
7 Correct 8 ms 16464 KB Output is correct
8 Correct 7 ms 16380 KB Output is correct
9 Correct 5 ms 16208 KB Output is correct
10 Correct 6 ms 16376 KB Output is correct
11 Correct 209 ms 41248 KB Output is correct
12 Correct 231 ms 42856 KB Output is correct
13 Correct 270 ms 44428 KB Output is correct
14 Correct 305 ms 47048 KB Output is correct
15 Correct 320 ms 48068 KB Output is correct
16 Correct 414 ms 54460 KB Output is correct
17 Correct 409 ms 57176 KB Output is correct
18 Correct 368 ms 54456 KB Output is correct
19 Correct 388 ms 59232 KB Output is correct
20 Correct 217 ms 41804 KB Output is correct
21 Correct 189 ms 40520 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15952 KB Output is correct
2 Correct 6 ms 15952 KB Output is correct
3 Correct 6 ms 16208 KB Output is correct
4 Correct 8 ms 16208 KB Output is correct
5 Correct 7 ms 16464 KB Output is correct
6 Correct 6 ms 16208 KB Output is correct
7 Correct 8 ms 16464 KB Output is correct
8 Correct 7 ms 16380 KB Output is correct
9 Correct 5 ms 16208 KB Output is correct
10 Correct 6 ms 16376 KB Output is correct
11 Correct 209 ms 41248 KB Output is correct
12 Correct 231 ms 42856 KB Output is correct
13 Correct 270 ms 44428 KB Output is correct
14 Correct 305 ms 47048 KB Output is correct
15 Correct 320 ms 48068 KB Output is correct
16 Correct 414 ms 54460 KB Output is correct
17 Correct 409 ms 57176 KB Output is correct
18 Correct 368 ms 54456 KB Output is correct
19 Correct 388 ms 59232 KB Output is correct
20 Correct 217 ms 41804 KB Output is correct
21 Correct 189 ms 40520 KB Output is correct
22 Correct 415 ms 58256 KB Output is correct
23 Correct 413 ms 55464 KB Output is correct
24 Correct 395 ms 55568 KB Output is correct
25 Correct 409 ms 63928 KB Output is correct
26 Correct 382 ms 57568 KB Output is correct
27 Correct 419 ms 55736 KB Output is correct
28 Correct 65 ms 20648 KB Output is correct
29 Correct 230 ms 42072 KB Output is correct
30 Correct 226 ms 42360 KB Output is correct
31 Correct 238 ms 42880 KB Output is correct
32 Correct 255 ms 46152 KB Output is correct