oj.uz

답안 #896761

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
896761 2024-01-02T05:40:27 Z qrno One-Way Streets (CEOI17_oneway) C++17
0 / 100
 1 ms 344 KB 
#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 dfs(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) {
      dfs(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);
  dfs(0, -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
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -