oj.uz

Submission #35892

# Submission time Handle Problem Language Result Execution time Memory
35892 2017-12-02T05:35:16 Z funcsr One-Way Streets (CEOI17_oneway) C++14
100 / 100
 363 ms 23852 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14908 KB Output is correct
2 Correct 0 ms 14908 KB Output is correct
3 Correct 0 ms 14908 KB Output is correct
4 Correct 0 ms 14908 KB Output is correct
5 Correct 3 ms 14908 KB Output is correct
6 Correct 0 ms 14908 KB Output is correct
7 Correct 3 ms 14908 KB Output is correct
8 Correct 0 ms 14908 KB Output is correct
9 Correct 3 ms 14908 KB Output is correct
10 Correct 3 ms 14908 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14908 KB Output is correct
2 Correct 0 ms 14908 KB Output is correct
3 Correct 0 ms 14908 KB Output is correct
4 Correct 0 ms 14908 KB Output is correct
5 Correct 3 ms 14908 KB Output is correct
6 Correct 0 ms 14908 KB Output is correct
7 Correct 3 ms 14908 KB Output is correct
8 Correct 0 ms 14908 KB Output is correct
9 Correct 3 ms 14908 KB Output is correct
10 Correct 3 ms 14908 KB Output is correct
11 Correct 149 ms 18460 KB Output is correct
12 Correct 99 ms 18948 KB Output is correct
13 Correct 139 ms 19740 KB Output is correct
14 Correct 179 ms 20424 KB Output is correct
15 Correct 176 ms 20752 KB Output is correct
16 Correct 166 ms 19388 KB Output is correct
17 Correct 189 ms 20844 KB Output is correct
18 Correct 166 ms 19388 KB Output is correct
19 Correct 169 ms 21972 KB Output is correct
20 Correct 109 ms 18732 KB Output is correct
21 Correct 116 ms 18580 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14908 KB Output is correct
2 Correct 0 ms 14908 KB Output is correct
3 Correct 0 ms 14908 KB Output is correct
4 Correct 0 ms 14908 KB Output is correct
5 Correct 3 ms 14908 KB Output is correct
6 Correct 0 ms 14908 KB Output is correct
7 Correct 3 ms 14908 KB Output is correct
8 Correct 0 ms 14908 KB Output is correct
9 Correct 3 ms 14908 KB Output is correct
10 Correct 3 ms 14908 KB Output is correct
11 Correct 149 ms 18460 KB Output is correct
12 Correct 99 ms 18948 KB Output is correct
13 Correct 139 ms 19740 KB Output is correct
14 Correct 179 ms 20424 KB Output is correct
15 Correct 176 ms 20752 KB Output is correct
16 Correct 166 ms 19388 KB Output is correct
17 Correct 189 ms 20844 KB Output is correct
18 Correct 166 ms 19388 KB Output is correct
19 Correct 169 ms 21972 KB Output is correct
20 Correct 109 ms 18732 KB Output is correct
21 Correct 116 ms 18580 KB Output is correct
22 Correct 363 ms 20836 KB Output is correct
23 Correct 309 ms 19256 KB Output is correct
24 Correct 289 ms 19388 KB Output is correct
25 Correct 343 ms 23852 KB Output is correct
26 Correct 323 ms 20416 KB Output is correct
27 Correct 319 ms 19300 KB Output is correct
28 Correct 93 ms 17020 KB Output is correct
29 Correct 169 ms 18488 KB Output is correct
30 Correct 213 ms 18576 KB Output is correct
31 Correct 176 ms 18764 KB Output is correct
32 Correct 296 ms 19860 KB Output is correct