제출 #1172946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172946		escobrand	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	6 ms	12360 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,q;
const int maxn = 1e5 + 10,maxv = 20;
struct bruh
{
  int XX,XXX,XXXX;
};
vector<bruh> a[maxn];
bool c[maxn],e[maxn],need[maxn];
int low[maxn],de[maxn],tim[maxn],ans[maxn],p[maxn][maxv];
set<int> from[maxn],to[maxn];

void dfs(int i,int pa)
{
  low[i] = tim[i] = ++t;
  c[i] = 1;
  de[i] = de[pa]+1;
  for(auto [k,id,ch] : a[i])
  {
    if(k == pa)continue;
    if(c[k])low[i] = min(low[i],tim[k]);
    else
    {
      dfs(k,i);
      low[i] = min(low[i],low[k]);
      p[k][0] = i;
      if(low[k] > tim[i])need[id] = 1;
    }
  }
}

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 i,int j)
{
  if(de[i] < de[j])swap(i,j);
  i = lift(i,de[i] - de[j]);
  if(i == j)return i;
  for(int k = maxv-1;k>=0;k--)
  {
    if(p[i][k] != p[j][k])
    {
      i = p[i][k];
      j = p[j][k];
    }
  }
  return p[i][0];
}

void solve(int i,int pa)
{
  e[i] = 1;
  // cout<<i<<' '<<pa<<'\n';
  for(auto [k,id,ch]: a[i])
  {
    if(k == pa)continue;
    if(!e[k])
    {
      solve(k,i);
      if(need[id])
      {
        if(from[k].size())ans[id] = ch;
        else if(to[k].size())ans[id] = 3- ch;
      }
      
      if(to[i].size() < to[k].size())swap(to[i],to[k]);
      if(from[i].size() < from[k].size())swap(from[i],from[k]);
      for(int l : from[k]) from[i].insert(l);
      for(int l : to[k]) to[i].insert(l);
    }
  }
  from[i].erase(de[i]);
  to[i].erase(de[i]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.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++)
    {
      t = 0;
      if(!c[i])dfs(i,0);
    }
    
    for(j = 1;j<maxv;j++)
    {
      for(i = 1;i<=n;i++)
      {
        p[i][j] = p[p[i][j-1]][j-1];
      }
    }
    
    
    cin>>q;
    while(q--)
    {
      cin>>u>>v;
      int tmp = lca(u,v);
      // cout<<tmp<<'\n';
      if(u != tmp) to[u].insert(de[tmp]);
      if(v != tmp) from[v].insert(de[tmp]);
    }
    for(i = 1;i<=n;i++)
    {
      if(!e[i])solve(i,0);
    }
    
    
    for(i = 0;i<m;i++)
    {
      if(ans[i] == 0)cout<<'B';
      else if(ans[i] == 1)cout<<'R';
      else cout<<'L';
    }
    
    
    
    
    return 0;
}

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