제출 #1259478

#제출 시각아이디문제언어결과실행 시간메모리
1259478danghuyOne-Way Streets (CEOI17_oneway)C++20
0 / 100
5 ms7488 KiB
#include <bits/stdc++.h>
using namespace std;
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
#define si size()
#define fi first
#define se second
#define ll int
#define sr sort
#define pb push_back
const ll MAXN=1e5+5,MOD=1e6,LG=19;
ll n,m,j,k,p,i,f,dem,ans,t,l,r=1,timedfs,id[MAXN],num[MAXN];
ll low[MAXN],mark[MAXN],a[MAXN],b[MAXN],up[MAXN][20];
ll goup[MAXN],godown[MAXN],congoup[MAXN],congodown[MAXN],cntup[MAXN],cntdown[MAXN];
ll h[MAXN],par[MAXN],bripar[MAXN];
stack<ll> scc;
vector<pair<ll,ll>> adj[MAXN],adj1[MAXN];
vector<ll> child[MAXN];
map<pair<ll,ll>,ll> ma;
ll comp;

void dfs(ll st,ll pre){
    num[st]=low[st]=++timedfs;
    scc.push(st);
    for(auto x:adj[st]){
        if(x.fi==pre) continue;
        if(!num[x.fi]){
            dfs(x.fi,st);
            low[st]=min(low[st],low[x.fi]);
        }
        else {  
            low[st]=min(low[st],num[x.fi]);
        }
    }
    if(low[st]==num[st]){
        ++comp;
        while(true){
            ll v=scc.top(); scc.pop();
            id[v]=comp;
            if(v==st) break;
        }
    }
}

void dfs1(ll st,ll pre){
    for(auto x:adj1[st]){
        if(x.fi==pre) continue;
        h[x.fi]=h[st]+1;
        up[x.fi][0]=st;
        par[x.fi]=st;
        bripar[x.fi]=x.se;
        child[st].pb(x.fi);
        for(ll j=1;j<=LG;j++){
            if(up[x.fi][j-1])
                up[x.fi][j]=up[up[x.fi][j-1]][j-1];
            else break;
        }
        dfs1(x.fi,st);
    }
}

ll lca(ll u,ll v){
    if(h[u]!=h[v]){
        if(h[u]<h[v]) swap(u,v);
        ll cnt=h[u]-h[v];
        for(ll j=0;j<=LG;j++)
            if((cnt>>j)&1) u=up[u][j];
    }
    if(u==v) return u;
    for(ll j=LG;j>=0;j--)
        if(up[u][j]!=up[v][j])
            u=up[u][j],v=up[v][j];
    return up[u][0];
}

void gou(ll st,ll en){
    ll cnt=0;
    while(st!=en){
        cnt+=goup[st];
        cnt+=congoup[st];
        goup[st]=0;
        congoup[st]=0;
        cntup[bripar[st]]+=cnt;
        st=par[st];
    }
}

void godo(ll st,ll cnt,ll pre){
    cntdown[bripar[st]]+=cnt;
    cnt+=congodown[st]+godown[st];
    godown[st]=0;
    congodown[st]=0;
    for(ll x:child[st]){
        godo(x,cnt,pre);
    }
    if(child[st].size()==0)
        gou(st,pre);
}

int main(){ 
    ios::sync_with_stdio(false);    
    cin.tie(nullptr);cout.tie(0);

    cin>>n>>m;
    for(i=1;i<=m;i++){
        ll u,v;
        cin>>u>>v;
        a[i]=u,b[i]=v;
        adj[u].pb({v,i});
        adj[v].pb({u,i});
        ma[{min(u,v),max(u,v)}]++;
    }

    for(i=1;i<=n;i++)
        if(!num[i])
            dfs(i,i);

    unordered_set<ll> s;
    for(i=1;i<=m;i++){
        if(id[a[i]]==id[b[i]] || ma[{min(a[i],b[i]),max(a[i],b[i])}]>1)
            mark[i]=2;
        else{
            adj1[id[a[i]]].pb({id[b[i]],i});
            adj1[id[b[i]]].pb({id[a[i]],i});
            s.insert(id[a[i]]);
            s.insert(id[b[i]]);
        }
    }

    vector<ll> c;
    for(ll x:s){
        if(h[x]) continue;
        c.pb(x);
        dfs1(x,x);
    }

    cin>>k;
    for(i=1;i<=k;i++){
        ll u,v;
        cin>>u>>v;
        u=id[u],v=id[v];
        ll k=lca(u,v);
        congoup[k]--;
        congodown[v]--;
        goup[u]++;
        godown[k]++;
    }

    for(ll x:c){
        godo(x,0,x);
    }

    for(i=1;i<=m;i++){
        if(!mark[i]){
            ll f=(h[id[a[i]]]<h[id[b[i]]]?0:1);
            if(cntup[i])
                mark[i]=!f;
            else if(cntdown[i]) mark[i]=f;
            else mark[i]=2;
        }
    }

    for(i=1;i<=m;i++){
        if(mark[i]==0)
            cout<<'R';
        else if(mark[i]==1)
            cout<<'L';
        else cout<<'B';
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...