Submission #896781

#	Time	Username	Problem	Language	Result	Execution time	Memory
896781		qrno	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	77 ms	16048 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

int N, M, P;
vector<vector<pair<int, int>>> G;
vector<pair<int, int>> E;

vector<int> req;

int TIMER = -1;
stack<int> S;
vector<int> tin, low;

int cc = -1;
vector<int> C;

void make_comp(int last) {
  cc++;
  int v = -1;
  do {
    v = S.top();
    S.pop();
    C[v] = cc;
  } while (v != last);
}

void tarjan(int v, int pidx) {
  S.push(v);
  tin[v] = low[v] = ++TIMER;
  for (auto [u, eidx] : G[v]) {
    if (eidx == pidx) continue;
    if (tin[u] == -1) {
      tarjan(u, eidx);
      req[v] += req[u];
    }
    low[v] = min(low[v], low[u]);
  }
  if (low[v] == tin[v]) make_comp(v);
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> N >> M;
  G.resize(N);
  for (int i = 0; i < M; i++) {
    int v, u; cin >> v >> u; v--, u--;
    G[v].push_back({u, i});
    G[u].push_back({v, i});
    E.push_back({v, u});
  }

  req.resize(N);
  cin >> P;
  for (int i = 0; i < P; i++) {
    int v, u; cin >> v >> u; v--, u--;
    req[v]++, req[u]--;
  }

  C.resize(N);
  tin.assign(N, -1);
  low.assign(N, -1);
  for (int i = 0; i < N; i++)
    if (tin[i] == -1)
      tarjan(i, -1);

  string ans(M, '?');
  for (int i = 0; i < M; i++) {
    auto [v, u] = E[i];
    if (C[v] == C[u]) { ans[i] = 'B'; continue; }
    if (tin[v] < tin[u]) {
      if (req[u] > 0) ans[i] = 'L';
      else if (req[u] == 0) ans[i] = 'B';
      else ans[i] = 'R';
    } else {
      if (req[v] > 0) ans[i] = 'R';
      else if (req[v] == 0) ans[i] = 'B';
      else ans[i] = 'L';
    }
  }

  cout << ans << endl;
}

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