oj.uz

Submission #398459

# Submission time Handle Problem Language Result Execution time Memory
398459 2021-05-04T10:36:00 Z model_code Inside information (BOI21_servers) C++17
100 / 100
 1326 ms 114860 KB 
/*
  full solution using centroid decomposition and a segment tree ~ O(Qlog^2N)
  Author: Erik Sünderhauf
*/
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
const int LG = 18;
vector<int> adj[N];

struct segtree {
  int n;
  vector<int> ch, seg;
  segtree() {}
  void upd(int l, int r, int k, int x, int v) {
    if (r < x || x < l) return;
    if (x <= l && r <= x) {
      seg[k] += v;
      return;
    }
    int m = (l+r) / 2;
    upd(l, m, k*2, x, v);
    upd(m+1, r, k*2+1, x, v);
    seg[k] = seg[k*2] + seg[k*2+1];
  }
  int qry(int l, int r, int k, int x) {
    if (r < x) return 0;
    if (x <= l) return seg[k];
    int m = (l+r) / 2;
    return qry(l, m, k*2, x) + qry(m+1, r, k*2+1, x);
  }
  void upd(int t) {
    int i = lower_bound(ch.begin(), ch.end(), t) - ch.begin();
    upd(0, n-1, 1, i, 1);
  }
  int qry(int t) {
    int i = lower_bound(ch.begin(), ch.end(), t) - ch.begin();
    return qry(0, n-1, 1, i);
  }
  void init() {
    seg.resize(4*n);
    fill(seg.begin(), seg.end(), 0);
  }
} seg[N];

// start lca
int lca_par[LG][N], depth[N];

int jump(int u, int d) {
  if (d < 0)
    return u;
  for (int i = 0; i < LG; i++)
    if (d >> i & 1)
      u = lca_par[i][u];
  return u;
}

int lca(int u, int v) {
  if (depth[u] > depth[v])
    swap(u, v);
  v = jump(v, depth[v] - depth[u]);
  if (u == v)
    return u;
  for (int i = LG-1; i >= 0; i--)
    if (lca_par[i][u] != lca_par[i][v])
      u = lca_par[i][u], v = lca_par[i][v];
  return lca_par[0][u];
}

void dfs(int u, int p) {
  for (int v: adj[u]) if (v != p) {
    depth[v] = depth[u] + 1;
    lca_par[0][v] = u;
    dfs(v, u);
  }
}
// end lca

// start centroid decomposition
int s[N], par[N], vis[N], cd_depth[N];

int getSz(int u, int p) {
  s[u] = 1;
  for (int v: adj[u])
    if (v != p && !vis[v])
      s[u] += getSz(v, u);
  return s[u];
}

int findCen(int u, int p, int n) {
  for (int v: adj[u])
    if (v != p && !vis[v] && s[v] > n/2)
      return findCen(v, u, n);
  return u;
}

void decompose(int c, int p) {
  c = findCen(c, -1, getSz(c, -1));
  par[c] = p;
  cd_depth[c] = ~p ? cd_depth[p] + 1 : 0;
  vis[c] = 1;
  for (int v: adj[c])
    if (!vis[v])
      decompose(v, c);
  vis[c] = 0;
}
// end centroid decomposition

// start hld
int hvy[N], root[N];

int init_hld(int u, int p) {
  s[u] = 1;
  hvy[u] = -1;
  root[u] = u;
  for (int v: adj[u]) {
    if (v != p) {
      s[u] += init_hld(v, u);
      if (hvy[u] < 0 || s[hvy[u]] < s[v])
        hvy[u] = v;
    }
  }
  return s[u];
}
// end hld

int hi[N][2], lo[N]; // walk up using edges with (decreasing / increasing) indices or down using edges with decreasing indices
int ind[N], curt = 0; // time when u and lca_par[0][u] where connected

void init(int n, vector<pair<int,int>> e) {
  for (auto [u, v]: e) {
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  // cd
  decompose(1, -1);
  for (int i = 1; i <= n; i++) {
    for (int j: adj[i]) {
      if (cd_depth[j] > cd_depth[i])
        seg[i].n++;
    }
    seg[i].init();
  }
  // lca
  dfs(1, -1);
  for (int i = 1; i < LG; i++)
    for (int j = 1; j <= n; j++)
      lca_par[i][j] = lca_par[i-1][lca_par[i-1][j]];
  // hld
  init_hld(1, -1);
  for (int i = 1; i <= n; i++)
    if (lca_par[0][i] == 0 || hvy[lca_par[0][i]] != i)
      for (int j = i; j != -1; j = hvy[j])
        root[j] = i;

  for (int i = 1; i <= n; i++)
    hi[i][0] = hi[i][1] = i, ind[i] = N+1, lo[i] = i;
}

int lower(int u, int v) {
  return depth[u] > depth[v] ? v : u;
}

int higher(int u, int v) {
  return depth[u] < depth[v] ? v : u;
}

// last node on the path from u to v
int last_node(int u, int v) {
  if (u == v)
    return u;
  int l = lca(u, v);
  if (l != v)
    return lca_par[0][v];
  return jump(u, depth[u] - depth[l] - 1);
}

// last node on the path from u to v
int first_node(int u, int v) {
  return last_node(v, u);
}

// when was this edge created?
int get_ind(int u, int v) {
  return u == v ? 0 : ind[higher(u, v)];
}

// is there a path from v to u where the indices of all edges increase
bool data(int u, int v) {
  if (u == v)
    return 1;
  int l = lca(u, v);
  if (lower(hi[u][0], l) != hi[u][0]) // walk down using increasing labels
    return 0;
  int x = v, y = -1;
  while (root[x] != root[l])
    y = root[x], x = lca_par[0][root[x]];
  // there is a light edge on the path from v to l -> we updated the whole subtree containing v already
  if (x != v && lower(hi[v][1], x) != hi[v][1])
    return 0;
  // we have to walk from x to l over heavy edges and we might have to check a light edge
  if (higher(lo[l], x) != lo[l] || (x != l && y != -1 && get_ind(y, x) > ind[x]))
    return 0;
  int pu = last_node(u, l), pv = last_node(v, l);
  return u == l || v == l || ind[pu] > ind[pv];
}

void xchg(int u, int v) {
  ++curt;
  if (cd_depth[u] > cd_depth[v])
    swap(u, v);
  if (depth[u] > depth[v])
    swap(u, v);
  ind[v] = curt;

  hi[v][0] = hi[u][0];
  if (hvy[u] != v) {
    function<void(int,int,int)> mrk = [&](int x, int y, int t) {
      hi[x][1] = u;
      for (int z: adj[x])
        if (z != y && get_ind(x, z) < t)
          mrk(z, x, get_ind(x, z));
    };
    mrk(v, u, curt);
  } else {
    lo[u] = lo[v];
  }

  if (cd_depth[u] > cd_depth[v])
    swap(u, v);
  seg[u].ch.push_back(curt);
  // update segment tree
  int c = u;
  while (c > 0) {
    if (data(u, c)) { // walk from c to u and then over the new edge
      int fst = first_node(c, u);
      if (fst == c)
        fst = v;
      int t = get_ind(c, fst);
      seg[c].upd(t);
    }
    c = par[c];
  }
}

int count(int u) {
  int c = u, r = 0;
  while (c > 0) {
    if (data(c, u)) {
      int lst = last_node(u, c);
      int t = get_ind(lst, c) + 1;
      r += seg[c].qry(t) + 1;
    }
    c = par[c];
  }
  return r;
}

int main() {
  int n, q; cin >> n >> q;
  vector<pair<int,int>> e(n-1);
  vector<array<int,3>> qr(n+q-1);
  for (int i = 0, j = 0; i < n+q-1; i++) {
    char t; int u, v = 0; cin >> t >> u;
    if (t != 'C')
      cin >> v;
    qr[i] = {t == 'C' ? 2 : (t == 'S' ? 0 : 1), u, v};
    if (t == 'S')
      e[j++] = make_pair(u, v);
  }
  init(n, e);
  for (int i = 0; i < n+q-1; i++) {
    int t = qr[i][0], u = qr[i][1], v = qr[i][2];
    if (t == 0) {
      xchg(u, v);
    } else if (t == 1) {
      bool b = data(u, v);
      cout << (b ? "yes\n" : "no\n");
    } else {
      int d = count(u);
      cout << d << "\n";
    }
  }
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 117 ms 80580 KB Output is correct
2 Correct 149 ms 81348 KB Output is correct
3 Correct 161 ms 81340 KB Output is correct
4 Correct 165 ms 81420 KB Output is correct
5 Correct 150 ms 81624 KB Output is correct
6 Correct 151 ms 81340 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 117 ms 80580 KB Output is correct
2 Correct 149 ms 81348 KB Output is correct
3 Correct 161 ms 81340 KB Output is correct
4 Correct 165 ms 81420 KB Output is correct
5 Correct 150 ms 81624 KB Output is correct
6 Correct 151 ms 81340 KB Output is correct
7 Correct 120 ms 80476 KB Output is correct
8 Correct 169 ms 81212 KB Output is correct
9 Correct 156 ms 81384 KB Output is correct
10 Correct 216 ms 81348 KB Output is correct
11 Correct 187 ms 81596 KB Output is correct
12 Correct 145 ms 81348 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 124 ms 80508 KB Output is correct
2 Correct 409 ms 103608 KB Output is correct
3 Correct 380 ms 103592 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 124 ms 80508 KB Output is correct
2 Correct 409 ms 103608 KB Output is correct
3 Correct 380 ms 103592 KB Output is correct
4 Correct 134 ms 80580 KB Output is correct
5 Correct 377 ms 103716 KB Output is correct
6 Correct 259 ms 103912 KB Output is correct
7 Correct 263 ms 103788 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 80540 KB Output is correct
2 Correct 829 ms 114676 KB Output is correct
3 Correct 840 ms 114696 KB Output is correct
4 Correct 627 ms 114764 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 80540 KB Output is correct
2 Correct 829 ms 114676 KB Output is correct
3 Correct 840 ms 114696 KB Output is correct
4 Correct 627 ms 114764 KB Output is correct
5 Correct 123 ms 80444 KB Output is correct
6 Correct 951 ms 114504 KB Output is correct
7 Correct 790 ms 114692 KB Output is correct
8 Correct 1077 ms 114516 KB Output is correct
9 Correct 1108 ms 114680 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 80492 KB Output is correct
2 Correct 522 ms 105028 KB Output is correct
3 Correct 559 ms 105164 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 80492 KB Output is correct
2 Correct 522 ms 105028 KB Output is correct
3 Correct 559 ms 105164 KB Output is correct
4 Correct 116 ms 80580 KB Output is correct
5 Correct 678 ms 105060 KB Output is correct
6 Correct 678 ms 104896 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 114 ms 80580 KB Output is correct
2 Correct 801 ms 114680 KB Output is correct
3 Correct 723 ms 114756 KB Output is correct
4 Correct 610 ms 114668 KB Output is correct
5 Correct 111 ms 80452 KB Output is correct
6 Correct 500 ms 104988 KB Output is correct
7 Correct 529 ms 104984 KB Output is correct
8 Correct 622 ms 104420 KB Output is correct
9 Correct 622 ms 104436 KB Output is correct
10 Correct 776 ms 108480 KB Output is correct
11 Correct 785 ms 107816 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 114 ms 80580 KB Output is correct
2 Correct 801 ms 114680 KB Output is correct
3 Correct 723 ms 114756 KB Output is correct
4 Correct 610 ms 114668 KB Output is correct
5 Correct 111 ms 80452 KB Output is correct
6 Correct 500 ms 104988 KB Output is correct
7 Correct 529 ms 104984 KB Output is correct
8 Correct 622 ms 104420 KB Output is correct
9 Correct 622 ms 104436 KB Output is correct
10 Correct 776 ms 108480 KB Output is correct
11 Correct 785 ms 107816 KB Output is correct
12 Correct 113 ms 80492 KB Output is correct
13 Correct 916 ms 114600 KB Output is correct
14 Correct 759 ms 114668 KB Output is correct
15 Correct 1039 ms 114588 KB Output is correct
16 Correct 1022 ms 114480 KB Output is correct
17 Correct 116 ms 80548 KB Output is correct
18 Correct 644 ms 105036 KB Output is correct
19 Correct 623 ms 104956 KB Output is correct
20 Correct 723 ms 104312 KB Output is correct
21 Correct 758 ms 104444 KB Output is correct
22 Correct 1228 ms 107836 KB Output is correct
23 Correct 1247 ms 109112 KB Output is correct
24 Correct 981 ms 108768 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 125 ms 80504 KB Output is correct
2 Correct 145 ms 81316 KB Output is correct
3 Correct 149 ms 81428 KB Output is correct
4 Correct 155 ms 81476 KB Output is correct
5 Correct 146 ms 81596 KB Output is correct
6 Correct 155 ms 81276 KB Output is correct
7 Correct 120 ms 80484 KB Output is correct
8 Correct 374 ms 103640 KB Output is correct
9 Correct 369 ms 103676 KB Output is correct
10 Correct 128 ms 80456 KB Output is correct
11 Correct 729 ms 114860 KB Output is correct
12 Correct 757 ms 114836 KB Output is correct
13 Correct 598 ms 114580 KB Output is correct
14 Correct 116 ms 80564 KB Output is correct
15 Correct 518 ms 104928 KB Output is correct
16 Correct 548 ms 105072 KB Output is correct
17 Correct 622 ms 104468 KB Output is correct
18 Correct 624 ms 104508 KB Output is correct
19 Correct 812 ms 108844 KB Output is correct
20 Correct 855 ms 107944 KB Output is correct
21 Correct 402 ms 103696 KB Output is correct
22 Correct 421 ms 103524 KB Output is correct
23 Correct 470 ms 103700 KB Output is correct
24 Correct 485 ms 103668 KB Output is correct
25 Correct 770 ms 107924 KB Output is correct
26 Correct 559 ms 104824 KB Output is correct
27 Correct 551 ms 104912 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 125 ms 80504 KB Output is correct
2 Correct 145 ms 81316 KB Output is correct
3 Correct 149 ms 81428 KB Output is correct
4 Correct 155 ms 81476 KB Output is correct
5 Correct 146 ms 81596 KB Output is correct
6 Correct 155 ms 81276 KB Output is correct
7 Correct 120 ms 80484 KB Output is correct
8 Correct 374 ms 103640 KB Output is correct
9 Correct 369 ms 103676 KB Output is correct
10 Correct 128 ms 80456 KB Output is correct
11 Correct 729 ms 114860 KB Output is correct
12 Correct 757 ms 114836 KB Output is correct
13 Correct 598 ms 114580 KB Output is correct
14 Correct 116 ms 80564 KB Output is correct
15 Correct 518 ms 104928 KB Output is correct
16 Correct 548 ms 105072 KB Output is correct
17 Correct 622 ms 104468 KB Output is correct
18 Correct 624 ms 104508 KB Output is correct
19 Correct 812 ms 108844 KB Output is correct
20 Correct 855 ms 107944 KB Output is correct
21 Correct 402 ms 103696 KB Output is correct
22 Correct 421 ms 103524 KB Output is correct
23 Correct 470 ms 103700 KB Output is correct
24 Correct 485 ms 103668 KB Output is correct
25 Correct 770 ms 107924 KB Output is correct
26 Correct 559 ms 104824 KB Output is correct
27 Correct 551 ms 104912 KB Output is correct
28 Correct 120 ms 80672 KB Output is correct
29 Correct 168 ms 81216 KB Output is correct
30 Correct 149 ms 81348 KB Output is correct
31 Correct 193 ms 81308 KB Output is correct
32 Correct 184 ms 81604 KB Output is correct
33 Correct 142 ms 81364 KB Output is correct
34 Correct 121 ms 80580 KB Output is correct
35 Correct 366 ms 103660 KB Output is correct
36 Correct 247 ms 103916 KB Output is correct
37 Correct 264 ms 103952 KB Output is correct
38 Correct 119 ms 80452 KB Output is correct
39 Correct 907 ms 114740 KB Output is correct
40 Correct 773 ms 114740 KB Output is correct
41 Correct 1010 ms 114648 KB Output is correct
42 Correct 1031 ms 114516 KB Output is correct
43 Correct 115 ms 80552 KB Output is correct
44 Correct 662 ms 104968 KB Output is correct
45 Correct 644 ms 104856 KB Output is correct
46 Correct 755 ms 104436 KB Output is correct
47 Correct 749 ms 104400 KB Output is correct
48 Correct 1246 ms 107952 KB Output is correct
49 Correct 1326 ms 109204 KB Output is correct
50 Correct 975 ms 108844 KB Output is correct
51 Correct 334 ms 103808 KB Output is correct
52 Correct 298 ms 104068 KB Output is correct
53 Correct 271 ms 103688 KB Output is correct
54 Correct 294 ms 103984 KB Output is correct
55 Correct 293 ms 103696 KB Output is correct
56 Correct 464 ms 103780 KB Output is correct
57 Correct 799 ms 108124 KB Output is correct
58 Correct 868 ms 104728 KB Output is correct
59 Correct 611 ms 104900 KB Output is correct