제출 #35892

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

oneway

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#define pb push_back
#define all(xs) xs.begin(), xs.end()
#define rep(i, n) for (int i=0; i<(n); i++)
using namespace std;
typedef pair<int, int> P;
#define _1 first
#define _2 second
struct UnionFind {
  int N;
  vector<int> U, R;
  UnionFind(int N) : N(N), U(N), R(N) {
    rep(i, N) U[i] = i, R[i] = 1;
  }
  int find(int x) {
    if (U[x] == x) return x;
    return U[x] = find(U[x]);
  }
  void unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (R[x] < R[y]) swap(x, y);
    U[y] = x;
    R[x] += R[y];
  }
};

int N, M, K;
vector<P> G[100000];
P E[100000];
bool bridge[100000];
bool up[100000], down[100000];

int R[100000], T[100000];
bool used[100000];
void dfs(int x, int p, int r) {
  used[x] = true;
  R[x] = r;
  for (P pp : G[x]) {
    int t = pp._1, pi = pp._2;
    if (pi == p) continue;
    if (used[t]) {
      if (R[t] < R[x]) T[t]++, T[x]--;
      continue;
    }
    dfs(t, pi, r+1);
  }
}
void dfs2(int x, int p) {
  used[x] = true;
  for (P pp : G[x]) {
    int t = pp._1, pi = pp._2;
    if (pi == p || used[t]) continue;
    dfs2(t, pi);
    T[x] += T[t];
  }
  if (p != -1 && T[x] == 0) bridge[p] = true;
}

int U[20][100000];
int W[2][100000];
void dfs3(int x, int p, int r) {
  used[x] = true;
  U[0][x] = p;
  R[x] = r;
  for (P pp : G[x]) {
    int t = pp._1;
    if (t == p) continue;
    dfs3(t, x, r+1);
  }
}
int lca(int x, int y) {
  if (R[x] < R[y]) swap(x, y);
  for (int k=19; k>=0; k--) if (((R[x]-R[y])>>k)&1) x = U[k][x];
  if (x == y) return x;
  for (int k=19; k>=0; k--) if (U[k][x] != U[k][y]) x = U[k][x], y = U[k][y];
  return U[0][x];
}
void dfs4(int x, int p, int pe) {
  for (P pp : G[x]) {
    int t = pp._1;
    if (t == p) continue;
    dfs4(t, x, pp._2);
    W[0][x] += W[0][t];
    W[1][x] += W[1][t];
  }
  if (p != -1) {
    assert(!W[0][x] || !W[1][x]);
    if      (W[0][x]) up[pe] = true;
    else if (W[1][x]) down[pe] = true;
    else up[pe] = down[pe] = true;
  }
}

signed main() {
  cin >> N >> M;
  rep(i, M) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    E[i] = P(a, b);
    if (a == b) {
      up[i] = down[i] = true;
      continue;
    }
    G[a].pb(P(b, i));
    G[b].pb(P(a, i));
  }
  rep(i, N) used[i] = false;
  rep(i, N) if (!used[i]) dfs(i, -1, 0);
  rep(i, N) used[i] = false;
  rep(i, N) if (!used[i]) dfs2(i, -1);

  // build a tree
  rep(i, N) G[i].clear();
  //rep(i, M) if(bridge[i])cout<<"i="<<i<<": "<<E[i]._1<<","<<E[i]._2<<" is a bridge\n";
  UnionFind uf(N);
  rep(i, M) if (!bridge[i]) {
    up[i] = down[i] = true;
    uf.unite(E[i]._1, E[i]._2);
  }
  rep(i, M) if (bridge[i]) {
    int u = uf.find(E[i]._1), v = uf.find(E[i]._2);
    G[u].pb(P(v, i));
    G[v].pb(P(u, i));
  }
  vector<int> roots;
  rep(i, N) used[i] = false;
  rep(i, N) if (uf.find(i) == i && !used[i]) dfs3(i, -1, 0), roots.pb(i);
  rep(k, 19) {
    rep(i, N) {
      if (uf.find(i) != i) continue;
      if (U[k][i] == -1) U[k+1][i] = -1;
      U[k+1][i] = U[k][U[k][i]];
    }
  }
  cin >> K;
  rep(i, K) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    x = uf.find(x), y = uf.find(y);
    if (x == y) continue;
    int g = lca(x, y);
    W[0][x]++, W[0][g]--; // x->g
    W[1][y]++, W[1][g]--; // y->g
  }
  for (int x : roots) dfs4(x, -1, -1);
  rep(i, M) if (bridge[i]) {
    int u = uf.find(E[i]._1), v = uf.find(E[i]._2);
    if (R[v] < R[u]) swap(up[i], down[i]);
  }

  rep(i, M) {
    assert(up[i] || down[i]);
    if (up[i] && down[i]) cout << 'B';
    else if (up[i]) cout << 'L';
    else if (down[i]) cout << 'R';
  }
  cout << '\n';
  return 0;
}

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