제출 #554554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
554554		MilosMilutinovic	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	86 ms	16988 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m;
  cin >> n >> m;
  vector<vector<pair<int, int>>> g(n);
  vector<tuple<int, int, int>> edges;
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    g[x].emplace_back(y, i);
    g[y].emplace_back(x, i);
    edges.emplace_back(x, y, i);
  }
  int p;
  cin >> p;
  vector<int> f(n);
  while (p--) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    f[x] += 1;
    f[y] -= 1;
  }
  vector<bool> was(n, false);
  vector<bool> bridge(m);
  vector<int> col(m);
  vector<int> tin(n);
  vector<int> low(n);
  int t = 0;
  function<void(int, int)> Dfs = [&](int v, int id) {
    was[v] = true;
    tin[v] = ++t;
    low[v] = t;
    for (auto& e : g[v]) {
      int to = e.first;
      int i = e.second;  
      if (i == id) {
        continue;
      }
      if (was[to]) {
        low[v] = min(low[v], tin[to]);
      } else {
        Dfs(to, i);      
        if (low[to] > tin[v]) {
          bridge[i] = true;
        }
        low[v] = min(low[v], low[to]);
        int cx = (get<0>(edges[i]) == v ? 1 : -1);
        int cy = (f[to] == 0 ? 0 : (f[to] > 0 ? 1 : -1));
        col[i] = cx * cy;
        f[v] += f[to];
      }
    }
  };
  for (int i = 0; i < n; i++) {
    if (!was[i]) {
      Dfs(i, -1);
    }
  }
  for (int i = 0; i < m; i++) {
    if (!bridge[i] || col[i] == 0) {
      cout << 'B';
    } else {  
      cout << (col[i] == 1 ? 'L' : 'R');
    }
  }
  cout << '\n';                                                   
  return 0;
}

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