Submission #974198

#	Time	Username	Problem	Language	Result	Execution time	Memory
974198		duckindog	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	79 ms	24828 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

const int N = 100'000 + 10;
int n, m, p;
int from[N], to[N];
vector<pair<int, bool>> ad[N];
int a[N], b[N];
namespace BCC { 
  vector<int> ad[N];
  int low[N], num[N], it;
  stack<int> st;
  int bcc[N], cc;
  void dfs(int u, int p = -1) { 
    low[u] = num[u] = ++it;
    st.push(u);
    
    bool pass = false;
    for (const auto& v : ad[u]) { 
      if (bcc[v] || v == p && !pass) { 
        pass = true;
        continue;
      }

      if (!low[v]) { 
        dfs(v, u);
        low[u] = min(low[u], low[v]);
      } else low[u] = min(low[u], num[v]);
    }
    
    if (low[u] == num[u]) { 
      bcc[u] = ++cc;
      while (st.top() != u) { 
        bcc[st.top()] = cc;
        st.pop();
      } st.pop();
    }
  }
}

int st[N], ed[N], it;
int par[N], d[N];
bool mk[N], vst[N];
void dfs(int u, int p = - 1) { 
  st[u] = ++it;
  for (const auto& [v, way] : ad[u]) { 
    if (v == p) continue;
    par[v] = u;
    d[v] = d[u] + 1;
    mk[v] = way;
    dfs(v, u);
  }
  ed[u] = it;
}
bool anc(int u, int v) { return st[u] <= st[v] && ed[u] >= ed[v]; }

int id[N];
int root(int u) { return !id[u] ? u : id[u] = root(id[u]); }
void add(int u, int v) { 
  u = root(u); v = root(v);
  if (u == v) return;
  if (d[u] > d[v]) swap(u, v);
  id[v] = u;
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;
  for (int i = 1; i <= m; ++i) cin >> from[i] >> to[i];
  cin >> p;
  for (int i = 1; i <= p; ++i) cin >> a[i] >> b[i];

  for (int i = 1; i <= m; ++i) { 
    int u = from[i], v = to[i];
    BCC::ad[u].push_back(v);
    BCC::ad[v].push_back(u);
  }

  for (int i = 1; i <= n; ++i) if (!BCC::low[i]) BCC::dfs(i);
  
  for (int i = 1; i <= m; ++i) { 
    int u = BCC::bcc[from[i]], v = BCC::bcc[to[i]];
    if (u == v) continue;
    ad[u].push_back({v, true});
    ad[v].push_back({u, false});
  }

  for (int i = 1; i <= n; ++i) if (!par[i]) dfs(par[i] = i);
  
  for (int i = 1; i <= p; ++i) { 
    int u = BCC::bcc[a[i]], v = BCC::bcc[b[i]];
    u = root(u); v = root(v);
    if (u == v) continue;
    for (int t = 1; t >= 0; --t) {
      vector<int> vt;
      while (!anc(u, v)) { 
        vt.push_back(u);
        u = root(par[root(u)]);
      } 
      
      for (const auto& x : vt) { 
        add(x, vt.end()[-1]);
        if (!vst[x]) mk[x] ^= t;
        vst[x] = true;
      }
      swap(u, v);
    }
  }
  
  for (int i = 1; i <= m; ++i) { 
    int u = from[i], v = to[i];

    int x = BCC::bcc[u], y = BCC::bcc[v];
    if (x == y) cout << 'B';
    else if (anc(x, y)) cout << (!vst[y] ? 'B' : mk[y] ? 'R' : 'L');
    else cout << (!vst[x] ? 'B' : mk[x] ? 'R' : 'L');
  } cout << "\n";
}

Compilation message (stderr)

oneway.cpp: In function 'void BCC::dfs(int, int)':
oneway.cpp:21:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   21 |       if (bcc[v] || v == p && !pass) {
      |                     ~~~~~~~^~~~~~~~

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