제출 #1363050

#제출 시각아이디문제언어결과실행 시간메모리
1363050NewtonabcOne-Way Streets (CEOI17_oneway)C++20
100 / 100
132 ms33056 KiB
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<pair<int,int>> adj[N];
vector<tuple<int,int,int>> g[N];
map<pair<int,int>,vector<int>> mp;
bool b[N],vs[N],vsb[N];
int f[N],dep[N],e[N],pa[N],val[N],an[N],ret[N],ui[N],vi[N],rev[N],ti,cp[N];
bool dir[N],ls[N];
bool crt[N];
int root(int x){if(pa[x]==x) return x; return pa[x]=root(pa[x]);}
void dfs(int u){
    //cout<<"vs" <<u <<"\n";
    vs[u]=1;
    for(auto [v,id]:adj[u]){
        if(dep[v]==0){
            //child
            dep[v]=dep[u]+1;
            e[v]=id;
            dfs(v);
            f[u]+=f[v];
        }
        else if(dep[v]<dep[u]){
            //backedge upward
            f[u]++;
        }
        else{
            //backedge downward
            b[id]=1;
            f[u]--;
        }
    }
    if(crt[u]==0) f[u]--;
    //cout<<u <<" " <<f[u] <<" " <<e[u] <<"\n";
    if(f[u]!=0 && crt[u]==0) b[e[u]]=1;
}
void efs(int u,int p){
    vsb[root(u)]=1;
    cp[root(u)]=ti;
    for(auto [v,id,type]:g[u]){
        if(v==p) continue;
        e[v]=id;
        an[v]=u;
        val[v]=val[u]+1;
        rev[v]=type;
        efs(v,u);
    }
}
int main(){
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
    dep[1]=1;
    vector<tuple<int,int,int>> lt;
    int n,m; cin>>n >>m;
    for(int i=0;i<m;i++){
        int u,v; cin>>u >>v;
        ui[i]=u,vi[i]=v;
        ls[i]=u<v;
        adj[u].push_back({v,i});
        adj[v].push_back({u,i});
        lt.push_back({u,v,i});
        mp[{min(u,v),max(u,v)}].push_back(i);
    }
    for(auto [p,v]:mp){
        if(v.size()>1){
            for(auto x:v) b[x]=1;
        }
    }
    //dfs(1);
    for(int i=1;i<=n;i++) if(!vs[i]) crt[i]=1,dfs(i);
    // for(int i=0;i<m;i++) cout<<b[i] <<" ";
    // cout<<"\n";
    // for(int i=17;i<=20;i++) cout<<f[i] <<" ";
    // cout<<"\n";
    for(int i=1;i<=n;i++) pa[i]=i;
    for(int i=0;i<m;i++){
        auto [u,v,x]=lt[i];
        ret[i]=-1;
        if(b[i]){
            if(root(u)!=root(v)) pa[root(u)]=root(v);
        }
    }
    for(auto [u,v,i]:lt){
        int ru=root(u),rv=root(v);
        //cout<<u <<" " <<v <<" " <<ru <<" " <<rv <<"\n";
        if(ru==rv) continue;
        g[ru].push_back({rv,i,0});
        g[rv].push_back({ru,i,1});
        //cout<<"edge" <<ru <<" " <<rv <<"\n";
    }
    int rt=root(1);
    for(int i=1;i<=n;i++) if(!vsb[root(i)]) ti++,efs(root(i),root(i));
    int q; cin>>q;
    while(q--){
        int u,v; cin>>u >>v;
        //cout<<"q" <<u <<" " <<v <<" " <<root(u) <<" " <<root(v) <<"\n";
        while(root(u)!=root(v)){
            int ru=root(u),rv=root(v);
            if(cp[ru]!=cp[rv]) break;
            //cout<<ru <<" " <<rv <<"\n";
            //cout<<ru <<" " <<rv <<" " <<val[ru] <<" " <<val[rv] <<"\n";
            if(val[ru]<val[rv]){
                ret[e[rv]]=rev[rv];
                pa[rv]=root(an[rv]);
            }
            else{
                ret[e[ru]]=rev[ru]^1;
                pa[ru]=root(an[ru]);
            }
        }
    }
    // for(int i=0;i<m;i++) cout<<ret[i] <<" ";
    // cout<<"\n";
    for(int i=0;i<m;i++){
        if(b[i] || ret[i]==-1) cout<<'B';
        else{
            if(ret[i]) cout<<'L';
            else cout<<'R';
        }
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…