oj.uz

답안 #1105424

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1105424 2024-10-26T10:08:11 Z asli_bg One-Way Streets (CEOI17_oneway) C++11
0 / 100
 7 ms 32848 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], 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;

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

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

    if(ind==0) return;

    if(!out[nd].empty()){ //benden çıkan varsa
        merge(out[ata],out[nd]);
        if(out[ata].count(ata)) out[ata].erase(ata);
        ans[ind]='R';
    }
    else if(!in[nd].empty()){
        merge(in[ata],in[nd]);
        if(in[ata].count(ata)) in[ata].erase(ata);
        ans[ind]='L';
    }
}

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++;
        tane[ind[{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);
            say++;
        }
    }  

    //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;
        if(comp[a]==comp[b]) continue;
        out[comp[a]].insert(comp[b]);
        in[comp[b]].insert(comp[a]);
    }

    ans.resize(m,'B');

    memset(vis,0,sizeof vis);

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

    for(auto el:ans) cout<<el;
    cout<<endl;
}

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

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 32848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 32848 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 32848 KB Output isn't correct
2 Halted 0 ms 0 KB -