Submission #1265136

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

oneway

#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(),v.end()
#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define mk make_pair
typedef pair<int,int> pii;

const int maxn = 1e5 + 10;
vector<pii> adj[maxn],com_adj[maxn];
int i,n,t,m,com_cnt,u,v;
int com[maxn],low[maxn],tim[maxn];
int dp[maxn];
char ans[maxn];
stack<int> st;

void dfs(int i,int pa)
{
  low[i] = tim[i] = ++t;
  st.push(i);
  bool through = 0;
  for(pii k : adj[i])
  {
    if(k.fi == pa && !through)
    {
      through = 1;
      continue;
    }
    if(tim[k.fi])low[i] = min(low[i],tim[k.fi]);
    else 
    {
      dfs(k.fi,i);
      low[i] = min(low[i],low[k.fi]);
    }
  }
  if(low[i] == tim[i])
  {
    ++com_cnt;
    while(st.top() != i)
    {
      com[st.top()] = com_cnt;
      st.pop();
    }
    com[st.top()] = com_cnt;
    st.pop();
  }
}

bool c[maxn];
void cal(int i,int pa)
{
  c[i] = 1;
  for(pii k : com_adj[i])
  {
    if(k.fi == pa)continue;
    cal(k.fi,i);
    dp[i] += dp[k.fi];
    dp[k.fi] *= k.se / abs(k.se);
    if(dp[k.fi] == 0)ans[abs(k.se)] = 'B';
    if(dp[k.fi] < 0)ans[abs(k.se)] = 'R';
    if(dp[k.fi] > 0)ans[abs(k.se)] = 'L';
  }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n>>m;
    for(i = 1;i<=m;i++)
    {
      cin>>u>>v;
      adj[u].pb(mk(v,i));
      adj[v].pb(mk(u,-i));
    }
    
    for(i = 1;i<=n;i++)
    {
      if(!tim[i])dfs(i,0);
    }
    
    for(i = 1;i<=n;i++)
    {
      for(pii k : adj[i])
      {
        if(com[i] != com[k.fi])com_adj[com[i]].pb(mk(com[k.fi],k.se));
        else ans[abs(k.se)] = 'B';
      }
    }
    
    cin>>t;
    while(t--)
    {
      cin>>u>>v;
      u = com[u];
      v = com[v];
      dp[u]++;
      dp[v]--;
    }
    for(i = 1;i<=com_cnt;i++)
    {
      if(!c[i])cal(i,0);
    }
    
    for(i = 1;i<=m;i++)cout<<ans[i];
    
    return 0;
}

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