Submission #1191630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191630		loom	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	2 ms	3648 KiB

oneway

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 5e18
#define nl '\n'

const int N = 1e5+1;
int dep[N], up[N][17], ix[N], op[N], vis[N], tin[N], low[N];
vector<tuple<int,int,int>> g[N];
char ans[N];
int cnt;

void dfs1(int v){
   vis[v] = 1;

   for(auto [ch, i, t] : g[v]){
      if(vis[ch]) continue;

      dep[ch] = dep[v]+1;
      up[ch][0] = v;
      ix[ch] = i;
      op[ch] = t;
      dfs1(ch);
   }
}

void dfs2(int v, int pe){
   vis[v] = 1;
   tin[v] = low[v] = cnt++;

   for(auto [ch, i, t] : g[v]){
      if(i == pe) continue;
      if(vis[ch]){
         low[v] = min(low[v], tin[ch]);
         ans[i] = 'B';
         continue;
      }

      dfs2(ch, i);
      low[v] = min(low[v], low[ch]);

      if(low[ch] <= tin[v]) ans[i] = 'B';
   }
}

int lca(int x, int y){
   if(dep[x] > dep[y]) swap(x, y);

   int k = dep[y] - dep[x];
   for(int i=0; i<17; i++){
      if(k & (1<<i)) y = up[y][i];
   }

   if(x == y) return x;

   for(int i=16; i>=0; i--){
      if(up[x][i] != up[y][i]){
         x = up[x][i];
         y = up[y][i];
      }
   }

   return up[x][0];
}

inline void solve(){
   int n, m;
   cin>>n>>m;
   for(int i=0; i<m; i++){
      int a, b;
      cin>>a>>b;
      if(a == b){
         ans[i] = 'B';
         continue;
      }

      g[a].push_back({b, i, 1});
      g[b].push_back({a, i, 0});
   }

   dfs1(1);
   for(int j=1; j<17; j++){
      for(int i=1; i<=n; i++){
         up[i][j] = up[up[i][j-1]][j-1];
      }
   }

   fill(ans, ans+N, ' ');

   int p;
   cin>>p;
   vector<tuple<int,int,int>> v;
   for(int i=0; i<p; i++){
      int x, y;
      cin>>x>>y;

      int l = lca(x, y);
      v.push_back({dep[l], x, y});
   }
   sort(v.begin(), v.end());

   for(auto [d, x, y] : v){
      int l = lca(x, y);
      
      while(x != l){
         if(ans[ix[x]] != ' ') break;
         ans[ix[x]] = (op[x] ? 'L' : 'R');
         x = up[x][0];
      }

      while(y != l){
         if(ans[ix[y]] != ' ') break;
         ans[ix[y]] = (op[y] ? 'R' : 'L');
         y = up[y][0];
      }
   }

   fill(vis, vis+N, 0);
   dfs2(1, -1);
   for(int i=0; i<m; i++) cout<<ans[i];
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

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