oj.uz

Submission #927913

# Submission time Handle Problem Language Result Execution time Memory
927913 2024-02-15T14:01:16 Z TAhmed33 One-Way Streets (CEOI17_oneway) C++
100 / 100
 841 ms 79044 KB 
#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
const int MAXN = 1e5 + 25;
struct SegmentTree {
  int lazy[2 * MAXN];
  int tree[2 * MAXN];
  void prop(int l, int r, int node) {
    if (lazy[node] == -1) return;
    if (l == r) {
      tree[node] = lazy[node];
    } else {
      lazy[tl] = lazy[tr] = lazy[node];
    }
    lazy[node] = -1;
  }
  void update(int l, int r, int a, int b, int c, int node) {
    if (l > b || r < a) return;
    if (l >= a && r <= b) {
      lazy[node] = c;
      prop(l, r, node);
      return;
    }
    update(l, mid, a, b, c, tl);
    update(mid + 1, r, a, b, c, tr);
  }
  int get(int l, int r, int a, int node) {
    prop(l, r, node);
    if (l == r) {
      return tree[node];
    }
    if (a <= mid) return get(l, mid, a, tl);
    return get(mid + 1, r, a, tr);
  }
};
SegmentTree cur;
set < pair < int, int >> bridges;
vector < int > adj1[MAXN];
int in [MAXN], low[MAXN];
bool vis[MAXN];
int t = 0;
vector < pair < int, int >> edges;
map < pair < int, int > , int > ans;
map < pair < int, int > , int > cnt;
void dfs(int pos, int par) {
  vis[pos] = 1;
  in [pos] = low[pos] = ++t;
  for (auto j: adj1[pos]) {
    if (j == par) continue;
    if (vis[j]) {
      low[pos] = min(low[pos], in [j]);
      continue;
    }
    dfs(j, pos);
    low[pos] = min(low[pos], low[j]);
    if (cnt[{
        j,
        pos
      }] == 1 && low[j] > in [pos]) {
      bridges.insert({
        pos,
        j
      });
    }
  }
}
struct DSU {
  int sze[MAXN], par[MAXN];
  void init() {
    for (int i = 1; i < MAXN; i++) {
      sze[i] = 1;
      par[i] = i;
    }
  }
  int find(int x) {
    return par[x] == x ? x : par[x] = find(par[x]);
  }
  void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    if (sze[x] > sze[y]) swap(x, y);
    sze[y] += sze[x];
    par[x] = y;
  }
};
DSU comps;
vector < pair < int, int >> adj[MAXN];
int p[MAXN];
int sze[MAXN];
int dep[MAXN];
void dfs2(int pos, int par) {
  p[pos] = par;
  sze[pos] = 1;
  vis[pos] = 1;
  for (int i = 0; i < (int) adj[pos].size(); i++) {
    if (adj[pos][i].first == par) {
      adj[pos].erase(adj[pos].begin() + i);
      break;
    }
  }
  for (auto & j: adj[pos]) {
    dep[j.first] = 1 + dep[pos];
    dfs2(j.first, pos);
    sze[pos] += sze[j.first];
    if (sze[j.first] > sze[adj[pos][0].first]) {
      swap(j, adj[pos][0]);
    }
  }
}
int in2[MAXN], out2[MAXN], nxt[MAXN];
void dfs3(int pos) {
  in2[pos] = ++t;
  for (auto j: adj[pos]) {
    nxt[j.first] = (j.first == adj[pos][0].first ? nxt[pos] : j.first);
    dfs3(j.first);
  }
  out2[pos] = t;
}
int uy;
map < int, int > xx, xx2;
int dp[32][MAXN];
int jump(int a, int b) {
  for (int i = 23; i >= 0; i--) {
    if ((b & (1 << i)) && dp[i][a]) a = dp[i][a];
    else if (b & (1 << i)) return 0;
  }
  return a;
}
int lca(int a, int b) {
  if (dep[a] < dep[b]) swap(a, b);
  int u = dep[a] - dep[b];
  a = jump(a, u);
  if (a == b) return a;
  for (int i = 23; i >= 0; i--) {
    int x = dp[i][a], y = dp[i][b];
    if (x && y && x != y) a = x, b = y;
  }
  return jump(a, 1);
}
void upd (int a, int b) {
  while (a) {
    if (in2[nxt[a]] <= in2[b]) {
      if (in2[b] < in2[a]) cur.update(1, uy, in2[b] + 1, in2[a], 1, 1);
      return;
    }
    cur.update(1, uy, in2[nxt[a]], in2[a], 1, 1);
    a = p[nxt[a]];
  }
}
void dow (int a, int b) {
  while (a) {
    if (in2[nxt[a]] <= in2[b]) {
      if (in2[b] < in2[a]) cur.update(1, uy, in2[b] + 1, in2[a], 2, 1);
      return;
    }
    cur.update(1, uy, in2[nxt[a]], in2[a], 2, 1);
    a = p[nxt[a]];
  }
}
void dfs5 (int pos, int par) {
  vis[pos] = 1;
  for (auto j : adj[pos]) {
    if (j.first != par) {
      dfs5(j.first, pos);
    }
    int x = cur.get(1, uy, in2[j.first], 1);
    pair <int, int> tt = edges[j.second];
    if (x == 0) {
      ans[tt] = 0;
      continue;
    }
    if (pos == xx[comps.find(tt.second)]) {
      x = 3 - x;
    }
    ans[tt] = x;
  }
}
int main() {
  memset(cur.lazy, -1, sizeof(cur.lazy));
  int n, m;
  cin >> n >> m;
  comps.init();
  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    cnt[{a, b}]++;
    cnt[{b, a}]++;
    edges.push_back({a, b});
    if (a == b) {
      ans[{a, b}] = ans[{b, a}] = 0;
      continue;
    }
    if (cnt[{a, b}] > 1) {
      ans[{a, b}] = ans[{b, a}] = 0;
      continue;
    }
    adj1[a].push_back(b);
    adj1[b].push_back(a);
  }
  for (int i = 1; i <= n; i++) {
    if (!vis[i]) {
      dfs(i, 0);
    }
  }
  for (auto[a, b]: edges) {
    if (!bridges.count({b, a}) && !bridges.count({a, b})) {
      comps.merge(a, b);
      ans[{a, b}] = ans[{b, a}] = 0;
    }
  }
  int uu = 0;
  set < int > pp;
  for (int i = 1; i <= n; i++) pp.insert(comps.find(i));
  uy = pp.size();
  for (auto i: pp) {
    xx[i] = xx.size() + 1;
  }
  for (auto i: xx) {
    xx2[i.second] = i.first;
  }
  for (auto[a, b]: edges) {
    if (bridges.count({b, a}) || bridges.count({a, b})) {
      adj[xx[comps.find(a)]].push_back({xx[comps.find(b)], uu});
      adj[xx[comps.find(b)]].push_back({xx[comps.find(a)], uu});
    }
    uu++;
  }
  memset(vis, 0, sizeof(vis));
  t = 0;
  for (int i = 1; i <= uy; i++) {
    if (!vis[i]) {
      dfs2(i, 0);
      nxt[i] = i;
      dfs3(i);
    }
  }
  for (int i = 1; i <= uy; i++) dp[0][i] = p[i];
  for (int i = 1; i <= 23; i++) {
    for (int j = 1; j <= uy; j++) {
      dp[i][j] = dp[i - 1][dp[i - 1][j]];
    }
  }
 /* for (int i = 1; i <= uy; i++) {
    cout << nxt[i] << " " << p[i] << " " << in2[i] << endl;
  }
  cout << "__________\n";*/
  int q;
  cin >> q;
  while (q--) {
    int a, b;
    cin >> a >> b;
    if (comps.find(a) == comps.find(b)) continue;
    a = xx[comps.find(a)];
    b = xx[comps.find(b)];
    int x = lca(a, b);
    //cout << a << " " << b << " " << x << endl;
    if (x != a) upd(a, x);
    if (x != b) dow(b, x);
  }
  memset(vis, 0, sizeof(vis));
  for (int i = 1; i <= uy; i++) {
    if (!vis[i]) {
      dfs5(i, 0);
    }
  }
  for (auto i : edges) {
    int z = ans[{i.first, i.second}];
    if (z == 0) cout << "B";
    else if (z == 2) cout << "R";
    else cout << "L";
  }
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:208:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  208 |   for (auto[a, b]: edges) {
      |            ^
oneway.cpp:224:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  224 |   for (auto[a, b]: edges) {
      |            ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20828 KB Output is correct
2 Correct 5 ms 20920 KB Output is correct
3 Correct 5 ms 21084 KB Output is correct
4 Correct 6 ms 21272 KB Output is correct
5 Correct 6 ms 21336 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 6 ms 21340 KB Output is correct
8 Correct 6 ms 21340 KB Output is correct
9 Correct 6 ms 21084 KB Output is correct
10 Correct 5 ms 21220 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20828 KB Output is correct
2 Correct 5 ms 20920 KB Output is correct
3 Correct 5 ms 21084 KB Output is correct
4 Correct 6 ms 21272 KB Output is correct
5 Correct 6 ms 21336 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 6 ms 21340 KB Output is correct
8 Correct 6 ms 21340 KB Output is correct
9 Correct 6 ms 21084 KB Output is correct
10 Correct 5 ms 21220 KB Output is correct
11 Correct 279 ms 51628 KB Output is correct
12 Correct 315 ms 52532 KB Output is correct
13 Correct 346 ms 54428 KB Output is correct
14 Correct 416 ms 59252 KB Output is correct
15 Correct 428 ms 60344 KB Output is correct
16 Correct 504 ms 67620 KB Output is correct
17 Correct 484 ms 71444 KB Output is correct
18 Correct 538 ms 67688 KB Output is correct
19 Correct 446 ms 73716 KB Output is correct
20 Correct 312 ms 52032 KB Output is correct
21 Correct 247 ms 50352 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 20828 KB Output is correct
2 Correct 5 ms 20920 KB Output is correct
3 Correct 5 ms 21084 KB Output is correct
4 Correct 6 ms 21272 KB Output is correct
5 Correct 6 ms 21336 KB Output is correct
6 Correct 4 ms 21084 KB Output is correct
7 Correct 6 ms 21340 KB Output is correct
8 Correct 6 ms 21340 KB Output is correct
9 Correct 6 ms 21084 KB Output is correct
10 Correct 5 ms 21220 KB Output is correct
11 Correct 279 ms 51628 KB Output is correct
12 Correct 315 ms 52532 KB Output is correct
13 Correct 346 ms 54428 KB Output is correct
14 Correct 416 ms 59252 KB Output is correct
15 Correct 428 ms 60344 KB Output is correct
16 Correct 504 ms 67620 KB Output is correct
17 Correct 484 ms 71444 KB Output is correct
18 Correct 538 ms 67688 KB Output is correct
19 Correct 446 ms 73716 KB Output is correct
20 Correct 312 ms 52032 KB Output is correct
21 Correct 247 ms 50352 KB Output is correct
22 Correct 747 ms 72460 KB Output is correct
23 Correct 841 ms 68796 KB Output is correct
24 Correct 838 ms 68832 KB Output is correct
25 Correct 710 ms 79044 KB Output is correct
26 Correct 729 ms 71940 KB Output is correct
27 Correct 741 ms 68864 KB Output is correct
28 Correct 153 ms 24256 KB Output is correct
29 Correct 305 ms 52264 KB Output is correct
30 Correct 333 ms 52456 KB Output is correct
31 Correct 295 ms 53200 KB Output is correct
32 Correct 445 ms 54464 KB Output is correct