oj.uz

Submission #570735

# Submission time Handle Problem Language Result Execution time Memory
570735 2022-05-31T08:00:59 Z Shin One-Way Streets (CEOI17_oneway) C++14
100 / 100
 236 ms 31760 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

const int LOG = 20;
const int N = 1e5 + 7;

vector<pair<int, int>> adj[N];
vector<pair<int, int>> g[N];

int n, m;
int num_comps;
int comps[N];
int num[N];
int low[N];
int timer;
int depth[N];
int par[N][LOG + 1];

bool R[N], L[N];
bool visited[N];
int sum_R[N], sum_L[N];

stack<int> st;
pair<int, int> e[N];

void dfs1(int u, int p) {
  num[u] = low[u] = ++ timer;
  st.push(u);
  for (pair<int, int> v: adj[u]) if (v.se != p) {
    if (num[v.fi]) {
      minimize(low[u], num[v.fi]);
    } else {
      dfs1(v.fi, v.se);
      minimize(low[u], low[v.fi]);
    }
  } 
  if (low[u] == num[u]) {
    int v;
    num_comps ++;
    do {
      v = st.top();
      st.pop();
      low[v] = num[v] = N;
      comps[v] = num_comps;
    } while (u != v);
  }
}

void dfs2(int u, int p) {
  visited[u] = true;
  par[u][0] = p;
  for (int i = 1; i <= LOG; i ++) {
    par[u][i] = par[par[u][i - 1]][i - 1];
  }
  for (pair<int, int> v: g[u]) if (v.fi != p) {
    depth[v.fi] = depth[u] + 1;
    dfs2(v.fi, u);
  }
}

int lca(int u, int v) {
  if (depth[v] > depth[u]) {
    swap(u, v);
  }
  int dist = depth[u] - depth[v];
  for (int i = LOG; i >= 0; i --) if ((dist >> i) & 1) {
    u = par[u][i];
  }
  if (u == v) {
    return u;
  }
  for (int i = LOG; i >= 0; i --) if (par[u][i] != par[v][i]) {
    u = par[u][i];
    v = par[v][i];
  }
  return par[u][0];
}

void build_tree() {
  for (int u = 1; u <= n; u ++) {
    for (pair<int, int> v: adj[u]) {
      if (comps[v.fi] != comps[u]) {
        g[comps[u]].emplace_back(comps[v.fi], v.se);
      }
    }
  }
  for (int i = 1; i <= num_comps; i ++) {
    if (!visited[i]) {
      dfs2(i, i);
    }
  }
}

void dfs3(int u, int p) {
  visited[u] = true;
  for (pair<int, int> v: g[u]) if (v.fi != p) {
    dfs3(v.fi, u);
    int f, t; tie(f, t) = e[v.se];
    bool dir = (u == comps[f] && v.fi == comps[t]);
    if (sum_R[v.fi]) {
      (dir ? R[v.se] = true : L[v.se] = true);
    }
    if (sum_L[v.fi]) {
      (dir ? L[v.se] = true : R[v.se] = true);
    }
    sum_L[u] += sum_L[v.fi];
    sum_R[u] += sum_R[v.fi];
  }
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1; i <= m; i ++) {
    int u, v; cin >> u >> v;
    e[i] = mp(u, v);
    adj[u].emplace_back(v, i);
    adj[v].emplace_back(u, i);
  } 
  for (int i = 1; i <= n; i ++) {
    if (!num[i]) {
      // assert(i == 1);
      dfs1(i, 0);
    }
  }
  build_tree();
  // for (int i = 1; i <= n; i ++) {
  //   cerr << i << " -> " << comps[i] << '\n';
  // }
  int q; cin >> q; 
  for (int i = 1; i <= q; i ++) {
    int u, v; cin >> u >> v;
    u = comps[u];
    v = comps[v];
    int w = lca(u, v);
    // u -> w -> v
    sum_L[u] ++;
    sum_L[w] --;
    sum_R[v] ++;
    sum_R[w] --;
    // cerr << w << '\n';
  }
  memset(visited, false, sizeof visited);
  for (int i = 1; i <= num_comps; i ++) {
    if (!visited[i])  {
      dfs3(i, -1);
    }
  }
  for (int i = 1; i <= m; i ++) {
    // cerr << L[i] << " " << R[i] << '\n';
    if (L[i] + R[i] != 1) {
      cout << "B";
    } else {
      cout << (R[i] ? "R" : "L");
    }
    // cerr << '\n';
  }
  return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5164 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 3 ms 5296 KB Output is correct
5 Correct 5 ms 5332 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 5 ms 5300 KB Output is correct
8 Correct 3 ms 5332 KB Output is correct
9 Correct 5 ms 5204 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5164 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 3 ms 5296 KB Output is correct
5 Correct 5 ms 5332 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 5 ms 5300 KB Output is correct
8 Correct 3 ms 5332 KB Output is correct
9 Correct 5 ms 5204 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct
11 Correct 38 ms 11556 KB Output is correct
12 Correct 40 ms 12576 KB Output is correct
13 Correct 49 ms 14284 KB Output is correct
14 Correct 77 ms 17684 KB Output is correct
15 Correct 95 ms 19040 KB Output is correct
16 Correct 123 ms 25176 KB Output is correct
17 Correct 101 ms 26992 KB Output is correct
18 Correct 107 ms 25268 KB Output is correct
19 Correct 101 ms 28380 KB Output is correct
20 Correct 44 ms 12160 KB Output is correct
21 Correct 45 ms 12116 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 3 ms 5164 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 3 ms 5296 KB Output is correct
5 Correct 5 ms 5332 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 5 ms 5300 KB Output is correct
8 Correct 3 ms 5332 KB Output is correct
9 Correct 5 ms 5204 KB Output is correct
10 Correct 4 ms 5204 KB Output is correct
11 Correct 38 ms 11556 KB Output is correct
12 Correct 40 ms 12576 KB Output is correct
13 Correct 49 ms 14284 KB Output is correct
14 Correct 77 ms 17684 KB Output is correct
15 Correct 95 ms 19040 KB Output is correct
16 Correct 123 ms 25176 KB Output is correct
17 Correct 101 ms 26992 KB Output is correct
18 Correct 107 ms 25268 KB Output is correct
19 Correct 101 ms 28380 KB Output is correct
20 Correct 44 ms 12160 KB Output is correct
21 Correct 45 ms 12116 KB Output is correct
22 Correct 236 ms 28112 KB Output is correct
23 Correct 164 ms 26260 KB Output is correct
24 Correct 164 ms 26484 KB Output is correct
25 Correct 228 ms 31760 KB Output is correct
26 Correct 169 ms 27812 KB Output is correct
27 Correct 131 ms 26400 KB Output is correct
28 Correct 32 ms 9284 KB Output is correct
29 Correct 59 ms 12776 KB Output is correct
30 Correct 60 ms 13096 KB Output is correct
31 Correct 89 ms 13436 KB Output is correct
32 Correct 126 ms 19404 KB Output is correct