Submission #1172970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172970		escobrand	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	103 ms	39816 KiB

oneway

#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(),v.end()
#define eb push_back
#define ll long long 
#define fi first
#define se second
int t,n,i,m,j,u,v,co,qr;
const int maxn = 3e5 + 10,maxv = 20;
int tim[maxn],low[maxn],id[maxn],p[maxn][maxv],de[maxn],ans[maxn],suma[maxn],sumb[maxn];
struct bruh
{
  int o,oo,ooo;
};
vector<bruh> a[maxn],tree[maxn];
stack<int> st;
bool e[maxn],f[maxn],g[maxn];

void dfs(int i,int p)
{
  tim[i] = low[i] = ++t;
  bool through = 0;
  st.push(i);
  for(auto [k,idx,ch] : a[i])
  {
    if(k == p && !through)
    {
      through = 1;
      continue;
    }
    if(tim[k])low[i] = min(low[i],tim[k]);
    else
    {
      dfs(k,i);
      low[i] = min(low[i],low[k]);
    }
  }
  if(low[i] == tim[i])
  {
    co++;
    while(st.top() != i)
    {
      id[st.top()] = co;
      st.pop();
    }
    id[st.top()] = co;
    st.pop();
  }
}

void cal(int i,int pa)
{
  e[i] = 1;
  for(auto [k,idx,ch] : a[i])
  {
    if(k == pa)continue;
    if(!e[k])
    {
      cal(k,i);
      if(low[k] > tim[i] && id[i] != id[k])
      {
        tree[id[i]].eb({id[k],idx,ch});
        tree[id[k]].eb({id[i],idx,3 - ch});
        // cout<<id[i]<<' '<<id[k]<<'\n';
      }
    }
  }
}

void bfs(int i,int pa)
{
  f[i] = 1;
  de[i] = de[pa]+1;
  for(auto [k,idx,ch] : tree[i])
  {
    if(k == pa||f[k])continue;
    
    bfs(k,i);
    p[k][0] = i;
  }
}

int lift(int i,int tmp)
{
  for(int j = 0;j<maxv;j++)
  {
    if((tmp>>j)&1)i = p[i][j];
  }
  return i;
}

int lca(int u,int v)
{
  if(de[u] < de[v])swap(u,v);
  u = lift(u,de[u] - de[v]);
  if(u == v)return u;
  for(int j = maxv-1;j>=0;j--)
  {
    if(p[u][j] != p[v][j])
    {
      u = p[u][j];
      v = p[v][j];
    }
  }
  return p[u][0];
}

void solve(int i,int pa)
{
  g[i] = 1;
  for(auto [k,idx,ch] : tree[i])
  {
    if(k == pa||g[k])continue;
    
    solve(k,i);
    suma[i]+= suma[k];
    sumb[i]+= sumb[k];
    
    if(suma[k] > 0)ans[idx] = 3 - ch;
    if(sumb[k] > 0)ans[idx] = ch;
  }
}

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n>>m;
    for(i = 0;i<m;i++)
    {
      cin>>u>>v;
      a[u].eb({v,i,1});
      a[v].eb({u,i,2});
    }
    for(i = 1;i<=n;i++)
    {
      if(!tim[i])dfs(i,0);
    }
    
    for(i = 1;i<=n;i++)
    {
      if(!e[i])cal(i,0);
    }
    
    for(i = 1;i<=co;i++)
    {
      if(!f[i])bfs(i,0);
    }
    
    for(j = 1;j<maxv;j++)
    {
      for(i = 1;i<=co;i++)
      {
        p[i][j] = p[p[i][j-1]][j-1];
      }
    }
    // for(i = 1;i<=n;i++)cout<<id[i]<<' ';
    
    cin>>qr;
    while(qr--)
    {
      cin>>u>>v;
      u = id[u];
      v = id[v];
      int lc = lca(u,v);
      suma[u]++;
      suma[lc]--;
      sumb[v]++;
      sumb[lc]--;
    }
    
    for(i = 1;i<=co;i++)
    {
      if(!g[i])solve(i,0);
    }
    
    for(i = 0;i<m;i++)
    {
      if(ans[i] == 1)cout<<'R';
      else if(ans[i] == 2)cout<<'L';
      else cout<<'B';
    }
    
    return 0;
}

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