Submission #1346657

#TimeUsernameProblemLanguageResultExecution timeMemory
1346657frogzzOne-Way Streets (CEOI17_oneway)C++20
100 / 100
200 ms55248 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,start,n)for(int i=start;i<n;i++)
template<typename T>using vc=vector<T>;
const int MAXN=2e5;
int tin[MAXN];int vis[MAXN];int dp[MAXN];int ti=0;
vector<int>child[MAXN];
vector<pair<int,int>>bridges;
void dfs(int u,int p){
  tin[u]=++ti;vis[u]=1;dp[u]=0;
  for(int v:child[u]){
    if(v==p)continue;
    if(vis[v]==1){
      if(tin[v]>tin[u])continue;
      dp[u]++;dp[v]--;
    }
    else{
      dfs(v,u);dp[u]+=dp[v];
    }
  }
  if(p!=-1&&dp[u]==0)bridges.push_back({min(u,p),max(u,p)});
}
vc<int>tree[MAXN];
int comp[MAXN];
int comp_cnt=0;
set<pair<int,int>>br_set;
void dfs_comp(int u){
  comp[u]=comp_cnt;
  for(int v:child[u]){
    if(comp[v])continue;
    if(br_set.count({min(u,v),max(u,v)})) continue;
    dfs_comp(v);
  }
}
int vis_tree[MAXN];
void make_tree(int n){
  for(auto b:bridges)br_set.insert(b);
  for(int i=1;i<=n;i++){
    if(!comp[i]){
      comp_cnt++;
      dfs_comp(i);
    }
  }
  for(auto b:bridges){
    int u=comp[b.first],v=comp[b.second];
    tree[u].push_back(v),tree[v].push_back(u);
  }
}
int up[MAXN][20];int dep[MAXN];
void dfs_lca(int u,int p=0,int d=0){
  up[u][0]=p;dep[u]=d;
  for(int i=1;i<20;i++)up[u][i]=up[up[u][i-1]][i-1];
  for(int v:tree[u]){
    if(v==p)continue;
    dfs_lca(v,u,d+1);
  }
}
int get_lca(int u,int v){
  if(dep[u]<dep[v])swap(u,v);
  int diff=dep[u]-dep[v];
  for(int i=0;i<20;i++)if((diff>>i)&1)u=up[u][i];
  if(u==v)return u;
  for(int i=19;i>=0;i--)if(up[u][i]!=up[v][i])u=up[u][i],v=up[v][i];
  return up[u][0];
}
int up_dp[MAXN];
int down_dp[MAXN];
void form(vector<pair<int,int>>&req){
  for(auto x:req){
     int LCA=get_lca(x.first,x.second);
     up_dp[x.first]++;up_dp[LCA]--;
     down_dp[x.second]++;down_dp[LCA]--;
  }
}
void final_dfs(int root,int p){
   vis_tree[root] = 1;
   for(int x:tree[root]){
    if(x!=p)final_dfs(x,root),down_dp[root]+=down_dp[x],up_dp[root]+=up_dp[x];
   }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;cin>>n>>m;
    rep(i,1,n+1)child[i].clear(),dp[i]=0,tin[i]=0,vis[i]=0;
    vc<pair<int,int>>in;
    map<pair<int,int>,int>cnt;
    rep(i,0,m){
     int ui,vi;cin>>ui>>vi;
      in.push_back({ui,vi}); 
      if(ui>vi)swap(ui,vi);
      cnt[{ui,vi}]++;
    }
    for(auto [edge,val]:cnt){
      child[edge.first].push_back(edge.second);
      child[edge.second].push_back(edge.first);
    }
    rep(i,1,n+1)if(!vis[i])dfs(i,-1);
    make_tree(n);
    int p;cin>>p;
    vector<pair<int,int>>req;
    while(p--){
      int ui,vi;cin>>ui>>vi;
      req.push_back({comp[ui],comp[vi]});
    }
     rep(i,1,comp_cnt+1)if(!dep[i])dfs_lca(i,0,1);
     form(req);
     rep(i,1,comp_cnt+1)if(!vis_tree[i]){
      vis_tree[i]=1;
      final_dfs(i,0);
     }
    string ans="";
    for(auto x:in){
      int cu=comp[x.first];
      int cv=comp[x.second];
      if(cu==cv||cnt[{min(x.first,x.second),max(x.first,x.second)}]>1){
        ans+="B";continue;
      }
      bool swapped=false;
      if(dep[cv]>dep[cu]){
        swap(cu,cv);
        swapped=true;
      }
      if(up_dp[cu]>0){
        ans+=(swapped?"L":"R");
      }
      else if(down_dp[cu]>0){
        ans+=(swapped?"R":"L");
      }
      else ans+="B";
    }
    cout<<ans<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...