oj.uz

답안 #647472

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
647472 2022-10-02T16:56:11 Z fahimcp495 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 141 ms 31428 KB 
#include<bits/stdc++.h>
using namespace std;

#define dbg(a)  cerr << #a << ": " << a << "\n"

using ll = long long;

struct graph {
  int n, t, sz;
  vector<vector<int>> adj;
  vector<int> tin, low, cmp;
  graph(int n): n(n),adj(n),tin(n),low(n),cmp(n){}
  void add_edge(int u, int v){
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  void dfs(int u, int p){
    tin[u]=low[u]=t++;
    int cnt=0;
    for(int v: adj[u]){
      if(v==p and ++cnt <= 1) continue;
      if(tin[v]!=-1)  low[u] = min(low[u], tin[v]);
      else {
        dfs(v,u);
        low[u] = min(low[u], low[v]);
      }
    }
  }
  void dfs2(int u, int p){
    if(p!=-1 and tin[p]>=low[u]) cmp[u] = cmp[p];
    else  cmp[u] = sz++;
    for(int v: adj[u]){
      if(cmp[v]==-1)  dfs2(v,u);
    }
  }
  void process_2ecc(){
    t = 0, sz = 0;
    for (int i = 0; i < n; ++i){
      tin[i] = low[i] = cmp[i] = -1;
    }
    for (int i = 0; i < n; ++i){
      if(tin[i]==-1)  dfs(i,-1);
    }
    for (int i = 0; i < n; ++i){
      if(cmp[i]==-1)  dfs2(i,-1);
    }
  }
};

const int N = 1e5+5, LG = 20;

int par[N][LG];
vector<array<int, 3>> adj[N];
vector<int> dep(N), tin(N, -1), tout(N), mn_left(N, N), mn_right(N, N);
char ans[N];
int t = 0;

void dfs(int u, int p) {
  tin[u] = t++;
  for (int k = 1; k < LG; ++k) {
    par[u][k] = par[par[u][k - 1]][k - 1];
  }
  for (auto [v, e, dir]: adj[u]) {
    if (v != p) {
      dep[v] = dep[u] + 1;
      par[v][0] = u;
      dfs(v, u);
    }
  }
  tout[u] = t++;
}

bool is_anc(int u, int v) {
  return (tin[u] <= tin[v] and tout[v] <= tout[u]);
}

int get_lca(int u, int v) {
  if (is_anc(u, v))  return u;
  if (is_anc(v, u))  return v;
  for (int j = LG - 1; j >= 0; --j) {
    if (!is_anc(par[u][j], v)) {
      u = par[u][j];
    }
  }
  return par[u][0];
}

vector<int> vis(N);

void dfs2(int u, int p) {
  vis[u] = 1;
  for (auto [v, e, dir]: adj[u]) {
    if (!vis[v]) {
      dfs2(v, u);
      if (mn_left[v] <= dep[u]) { // v -> u
        if (dir == 0) { // 
          ans[e] = 'L';
        }
        else {
          ans[e] = 'R';
        }
      }

      if (mn_right[v] <= dep[u]) {  // u -> v
        if (dir == 0) {
          ans[e] = 'R';
        }
        else {
          ans[e] = 'L';
        }
      }

      mn_left[u] = min(mn_left[u], mn_left[v]);
      mn_right[u] = min(mn_right[u], mn_right[v]);
    }
  }
}

void solve() {
  int n, m;  cin >> n >> m;
  graph g(n);
  vector<array<int, 2>> edges(m);
  for (auto &[u, v]: edges) {
    cin >> u >> v;  u--, v--;
    if (u != v) {
      g.add_edge(u, v);
    }
  }

  g.process_2ecc();

  for (int e = 0; e < m; ++e) {
    ans[e] = 'B';
    auto [u, v] = edges[e];
    u = g.cmp[u];
    v = g.cmp[v];
    if (u != v) {
      adj[u].push_back({v, e, 0});
      adj[v].push_back({u, e, 1});
    }
  }

  for (int u = 0; u < n; ++u) {
    if (tin[u] == -1) {
      par[u][0] = u;
      dfs(u, -1);
    }
  }

  int q;  cin >> q;
  while (q--) {
    int u, v;  cin >> u >> v;  u--, v--;
    u = g.cmp[u];
    v = g.cmp[v];
    int l = get_lca(u, v);
    mn_left[u] = min(mn_left[u], dep[l]);
    mn_right[v] = min(mn_right[v], dep[l]);
  }

  for (int u = 0; u < n; ++u) {
    if (!vis[u]) {
      dfs2(u, u);
    }
  }

  cout << ans << "\n";
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);

  int tc = 1;
  for (int t = 1; t <= tc; ++t) {
    solve();
  }
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 5056 KB Output is correct
4 Correct 4 ms 5168 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 3 ms 5056 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 5056 KB Output is correct
4 Correct 4 ms 5168 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 3 ms 5056 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 41 ms 11256 KB Output is correct
12 Correct 43 ms 13152 KB Output is correct
13 Correct 51 ms 16076 KB Output is correct
14 Correct 66 ms 20680 KB Output is correct
15 Correct 75 ms 22232 KB Output is correct
16 Correct 94 ms 25884 KB Output is correct
17 Correct 87 ms 27252 KB Output is correct
18 Correct 90 ms 25876 KB Output is correct
19 Correct 86 ms 28400 KB Output is correct
20 Correct 46 ms 15308 KB Output is correct
21 Correct 44 ms 15120 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 4 ms 4948 KB Output is correct
3 Correct 3 ms 5056 KB Output is correct
4 Correct 4 ms 5168 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 3 ms 5076 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 4 ms 5204 KB Output is correct
9 Correct 3 ms 5056 KB Output is correct
10 Correct 4 ms 5076 KB Output is correct
11 Correct 41 ms 11256 KB Output is correct
12 Correct 43 ms 13152 KB Output is correct
13 Correct 51 ms 16076 KB Output is correct
14 Correct 66 ms 20680 KB Output is correct
15 Correct 75 ms 22232 KB Output is correct
16 Correct 94 ms 25884 KB Output is correct
17 Correct 87 ms 27252 KB Output is correct
18 Correct 90 ms 25876 KB Output is correct
19 Correct 86 ms 28400 KB Output is correct
20 Correct 46 ms 15308 KB Output is correct
21 Correct 44 ms 15120 KB Output is correct
22 Correct 135 ms 28488 KB Output is correct
23 Correct 131 ms 26856 KB Output is correct
24 Correct 130 ms 27040 KB Output is correct
25 Correct 124 ms 31428 KB Output is correct
26 Correct 141 ms 28012 KB Output is correct
27 Correct 137 ms 27032 KB Output is correct
28 Correct 28 ms 8204 KB Output is correct
29 Correct 64 ms 16204 KB Output is correct
30 Correct 65 ms 16340 KB Output is correct
31 Correct 64 ms 16416 KB Output is correct
32 Correct 85 ms 20524 KB Output is correct