Submission #1362856

#TimeUsernameProblemLanguageResultExecution timeMemory
1362856NewtonabcOne-Way Streets (CEOI17_oneway)C++20
0 / 100
169 ms327680 KiB
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<pair<int,int>> adj[N],g[N];
map<pair<int,int>,vector<int>> mp;
bool b[N],vs[N];
int f[N],dep[N],e[N],pa[N],val[N],an[N],ret[N],ui[N],vi[N];
bool dir[N],ls[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";
    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(u!=1) f[u]--;
    //cout<<u <<" " <<f[u] <<" " <<e[u] <<"\n";
    if(f[u]!=0) b[e[u]]=1;
}
void efs(int u,int p){
    an[u]=p;
    for(auto [v,i]:g[u]){
        if(v==p) continue;
        e[v]=i;
        val[v]=val[u]+1;
        efs(v,u);
    }
}
int rec(int u,int i){
    if(ui[i]==u) return vi[i];
    return ui[i];
}
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;
        }
    }
    // for(int i=0;i<m;i++) cout<<b[i] <<" ";
    // cout<<"\n";
    dfs(1);
    // for(int i=0;i<m;i++){
    //     cout<<b[i] <<" ";
    // }
    for(int i=1;i<=n;i++) pa[i]=i;
    for(auto [u,v,i]:lt){
        if(b[i]==1){
            if(root(u)!=root(v)) pa[root(u)]=root(v);
        }
    }
    for(auto [u,v,i]:lt){
        if(b[i]==0){
            u=root(u),v=root(v);
            g[u].push_back({v,i});
            g[v].push_back({u,i});
        }
    }
    int rt=root(1);
    val[rt]=0;
    efs(rt,rt);
    int p; cin>>p;
    while(p--){
        int u,v; cin>>u >>v;
        while(root(u)!=root(v)){
            int ru=root(u),rv=root(v);
            if(val[ru]<val[rv]){
                //push rv up
                int tmp=rec(rv,e[rv]);
                pa[rv]=root(tmp);
                //traverse from tmp to rv
                //answer for edge e[rv]
                ret[e[rv]]=(tmp<rv)^(ls[e[rv]]);
            }
            else{
                int tmp=rec(u,e[ru]);
                pa[ru]=tmp;
                ret[e[ru]]=(tmp>ru)^(ls[e[ru]]);
            }
        }
    }
    for(int i=0;i<m;i++){
        if(b[i]) cout<<'B';
        else{
            if(ret[i]) cout<<'L';
            else cout<<'R';
        }
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...