Submission #1129152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129152		Luvidi	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	174 ms	31004 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back

const int maxn=1e5;
vector<pii> adj[maxn+1],ch[maxn+1];
int dp[maxn+1],rt[maxn+1],d[maxn+1],up[maxn+1][20],cnt[maxn+1][2];
bool vis[maxn+1];

void dfs(int v,int p){
    vis[v]=1;
    for(auto[u,i]:adj[v])if(i!=p){
        if(vis[u]){
            if(d[v]>d[u]){
                dp[v]++;
                dp[u]--;
            }
        }else{
            d[u]=d[v]+1;
            dfs(u,i);
            dp[v]+=dp[u];
        }
    }
}

void dfs2(int v){
    vis[v]=1;
    for(auto[u,i]:adj[v])if(!vis[u]){
        if(dp[u])rt[u]=rt[v];
        else{
            up[u][0]=rt[v];
            rt[u]=u;
            d[u]=d[rt[v]]+1;
            ch[rt[v]].pb({u,i});
        }
        dfs2(u);
    }
}

int lca(int u,int v){
    if(d[u]>d[v])swap(u,v);
    for(int i=19;i>-1;i--)if(d[v]-(1<<i)>=d[u])v=up[v][i];
    if(u==v)return u;
    for(int i=19;i>-1;i--)if(up[u][i]!=up[v][i]){
        u=up[u][i];
        v=up[v][i];
    }
    return up[u][0];
}

void dfs3(int v){
    vis[v]=1;
    for(auto[u,i]:ch[v]){
        dfs3(u);
        cnt[v][0]+=cnt[u][0];
        cnt[v][1]+=cnt[u][1];
    }
}

void solve() {
    int n,m;
    cin>>n>>m;
    pii ed[m];
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        adj[u].pb({v,i});
        adj[v].pb({u,i});
        ed[i]={u,v};
    }
    for(int i=1;i<=n;i++)if(!vis[i])dfs(i,-1);
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)up[i][0]=i;
    for(int i=1;i<=n;i++)if(!vis[i]){
        rt[i]=i;
        dfs2(i);
    }
    for(int x=1;x<20;x++){
        for(int i=1;i<=n;i++)up[i][x]=up[up[i][x-1]][x-1];
    }
    int p;
    cin>>p;
    while(p--){
        int u,v;
        cin>>u>>v;
        u=rt[u];
        v=rt[v];
        if(u==v)continue;
        int x=lca(u,v);
        cnt[u][0]++;
        cnt[x][0]--;
        cnt[v][1]++;
        cnt[x][1]--;
    }
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)if(!vis[i])dfs3(i);
    set<pii> s;
    for(int i=1;i<=n;i++)if(i==rt[i]){
        if(cnt[i][0])s.insert({i,up[i][0]});
        if(cnt[i][1])s.insert({up[i][0],i});
    }
    for(auto[u,v]:ed){
        // int u2=u,v2=v;
        u=rt[u];
        v=rt[v];
        if(s.count({u,v})){
            cout<<'R';
            // cout<<u2<<' '<<v2<<'\n';
        }else if(s.count({v,u})){
            cout<<'L';
            // cout<<v2<<' '<<u2<<'\n';
        }else{
            cout<<'B';
        }
    }
    cout<<'\n';
}

int main() {
    #ifdef FPO
        freopen("in","r",stdin);
        freopen("out","w",stdout);
    #endif
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40