oj.uz

답안 #850718

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
850718 2023-09-17T10:46:10 Z vjudge1 Inside information (BOI21_servers) C++17
100 / 100
 664 ms 173928 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

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 132060 KB Output is correct
2 Correct 94 ms 132512 KB Output is correct
3 Correct 90 ms 132644 KB Output is correct
4 Correct 91 ms 132692 KB Output is correct
5 Correct 88 ms 132880 KB Output is correct
6 Correct 90 ms 132688 KB Output is correct

Subtask #2
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 68 ms 132060 KB Output is correct
2 Correct 94 ms 132512 KB Output is correct
3 Correct 90 ms 132644 KB Output is correct
4 Correct 91 ms 132692 KB Output is correct
5 Correct 88 ms 132880 KB Output is correct
6 Correct 90 ms 132688 KB Output is correct
7 Correct 67 ms 132180 KB Output is correct
8 Correct 96 ms 132564 KB Output is correct
9 Correct 85 ms 132680 KB Output is correct
10 Correct 118 ms 132640 KB Output is correct
11 Correct 117 ms 132896 KB Output is correct
12 Correct 91 ms 132748 KB Output is correct

Subtask #3
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 132176 KB Output is correct
2 Correct 208 ms 160728 KB Output is correct
3 Correct 219 ms 160748 KB Output is correct

Subtask #4
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 132176 KB Output is correct
2 Correct 208 ms 160728 KB Output is correct
3 Correct 219 ms 160748 KB Output is correct
4 Correct 69 ms 132176 KB Output is correct
5 Correct 198 ms 160716 KB Output is correct
6 Correct 142 ms 160968 KB Output is correct
7 Correct 155 ms 160972 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 132040 KB Output is correct
2 Correct 396 ms 171684 KB Output is correct
3 Correct 401 ms 171872 KB Output is correct
4 Correct 362 ms 171812 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 132040 KB Output is correct
2 Correct 396 ms 171684 KB Output is correct
3 Correct 401 ms 171872 KB Output is correct
4 Correct 362 ms 171812 KB Output is correct
5 Correct 65 ms 132180 KB Output is correct
6 Correct 482 ms 171680 KB Output is correct
7 Correct 487 ms 171904 KB Output is correct
8 Correct 624 ms 171620 KB Output is correct
9 Correct 530 ms 171688 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 132044 KB Output is correct
2 Correct 273 ms 162124 KB Output is correct
3 Correct 321 ms 162360 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 132044 KB Output is correct
2 Correct 273 ms 162124 KB Output is correct
3 Correct 321 ms 162360 KB Output is correct
4 Correct 67 ms 132152 KB Output is correct
5 Correct 362 ms 164032 KB Output is correct
6 Correct 369 ms 163972 KB Output is correct

Subtask #9
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 132180 KB Output is correct
2 Correct 441 ms 172016 KB Output is correct
3 Correct 419 ms 171692 KB Output is correct
4 Correct 384 ms 171848 KB Output is correct
5 Correct 68 ms 132176 KB Output is correct
6 Correct 315 ms 162468 KB Output is correct
7 Correct 318 ms 162256 KB Output is correct
8 Correct 377 ms 161448 KB Output is correct
9 Correct 374 ms 161684 KB Output is correct
10 Correct 448 ms 165492 KB Output is correct
11 Correct 458 ms 165028 KB Output is correct

Subtask #10
12.5 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 132180 KB Output is correct
2 Correct 441 ms 172016 KB Output is correct
3 Correct 419 ms 171692 KB Output is correct
4 Correct 384 ms 171848 KB Output is correct
5 Correct 68 ms 132176 KB Output is correct
6 Correct 315 ms 162468 KB Output is correct
7 Correct 318 ms 162256 KB Output is correct
8 Correct 377 ms 161448 KB Output is correct
9 Correct 374 ms 161684 KB Output is correct
10 Correct 448 ms 165492 KB Output is correct
11 Correct 458 ms 165028 KB Output is correct
12 Correct 68 ms 132044 KB Output is correct
13 Correct 452 ms 171600 KB Output is correct
14 Correct 479 ms 171760 KB Output is correct
15 Correct 562 ms 172196 KB Output is correct
16 Correct 536 ms 171572 KB Output is correct
17 Correct 67 ms 132064 KB Output is correct
18 Correct 352 ms 164000 KB Output is correct
19 Correct 377 ms 163748 KB Output is correct
20 Correct 415 ms 163232 KB Output is correct
21 Correct 403 ms 163492 KB Output is correct
22 Correct 604 ms 166816 KB Output is correct
23 Correct 664 ms 167904 KB Output is correct
24 Correct 487 ms 167736 KB Output is correct

Subtask #11
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 132096 KB Output is correct
2 Correct 88 ms 132436 KB Output is correct
3 Correct 101 ms 132624 KB Output is correct
4 Correct 94 ms 132692 KB Output is correct
5 Correct 96 ms 132892 KB Output is correct
6 Correct 87 ms 132688 KB Output is correct
7 Correct 69 ms 132412 KB Output is correct
8 Correct 195 ms 160724 KB Output is correct
9 Correct 201 ms 160796 KB Output is correct
10 Correct 63 ms 132196 KB Output is correct
11 Correct 446 ms 171896 KB Output is correct
12 Correct 412 ms 172144 KB Output is correct
13 Correct 385 ms 171688 KB Output is correct
14 Correct 67 ms 132148 KB Output is correct
15 Correct 289 ms 162180 KB Output is correct
16 Correct 321 ms 162244 KB Output is correct
17 Correct 351 ms 161628 KB Output is correct
18 Correct 367 ms 161616 KB Output is correct
19 Correct 441 ms 165544 KB Output is correct
20 Correct 472 ms 165120 KB Output is correct
21 Correct 248 ms 160532 KB Output is correct
22 Correct 216 ms 160540 KB Output is correct
23 Correct 284 ms 160956 KB Output is correct
24 Correct 290 ms 160956 KB Output is correct
25 Correct 475 ms 165148 KB Output is correct
26 Correct 301 ms 161888 KB Output is correct
27 Correct 305 ms 162016 KB Output is correct

Subtask #12
17.5 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 132096 KB Output is correct
2 Correct 88 ms 132436 KB Output is correct
3 Correct 101 ms 132624 KB Output is correct
4 Correct 94 ms 132692 KB Output is correct
5 Correct 96 ms 132892 KB Output is correct
6 Correct 87 ms 132688 KB Output is correct
7 Correct 69 ms 132412 KB Output is correct
8 Correct 195 ms 160724 KB Output is correct
9 Correct 201 ms 160796 KB Output is correct
10 Correct 63 ms 132196 KB Output is correct
11 Correct 446 ms 171896 KB Output is correct
12 Correct 412 ms 172144 KB Output is correct
13 Correct 385 ms 171688 KB Output is correct
14 Correct 67 ms 132148 KB Output is correct
15 Correct 289 ms 162180 KB Output is correct
16 Correct 321 ms 162244 KB Output is correct
17 Correct 351 ms 161628 KB Output is correct
18 Correct 367 ms 161616 KB Output is correct
19 Correct 441 ms 165544 KB Output is correct
20 Correct 472 ms 165120 KB Output is correct
21 Correct 248 ms 160532 KB Output is correct
22 Correct 216 ms 160540 KB Output is correct
23 Correct 284 ms 160956 KB Output is correct
24 Correct 290 ms 160956 KB Output is correct
25 Correct 475 ms 165148 KB Output is correct
26 Correct 301 ms 161888 KB Output is correct
27 Correct 305 ms 162016 KB Output is correct
28 Correct 70 ms 132180 KB Output is correct
29 Correct 98 ms 133312 KB Output is correct
30 Correct 89 ms 133400 KB Output is correct
31 Correct 118 ms 133460 KB Output is correct
32 Correct 114 ms 133604 KB Output is correct
33 Correct 81 ms 133460 KB Output is correct
34 Correct 69 ms 132944 KB Output is correct
35 Correct 214 ms 162240 KB Output is correct
36 Correct 158 ms 162100 KB Output is correct
37 Correct 152 ms 162124 KB Output is correct
38 Correct 68 ms 132948 KB Output is correct
39 Correct 513 ms 173508 KB Output is correct
40 Correct 494 ms 173928 KB Output is correct
41 Correct 511 ms 173252 KB Output is correct
42 Correct 551 ms 173180 KB Output is correct
43 Correct 67 ms 132944 KB Output is correct
44 Correct 366 ms 164064 KB Output is correct
45 Correct 336 ms 163788 KB Output is correct
46 Correct 393 ms 163232 KB Output is correct
47 Correct 445 ms 163648 KB Output is correct
48 Correct 618 ms 166988 KB Output is correct
49 Correct 581 ms 167848 KB Output is correct
50 Correct 479 ms 167768 KB Output is correct
51 Correct 192 ms 162940 KB Output is correct
52 Correct 188 ms 162844 KB Output is correct
53 Correct 165 ms 162568 KB Output is correct
54 Correct 180 ms 162844 KB Output is correct
55 Correct 178 ms 162888 KB Output is correct
56 Correct 266 ms 162820 KB Output is correct
57 Correct 409 ms 166692 KB Output is correct
58 Correct 429 ms 163396 KB Output is correct
59 Correct 345 ms 164288 KB Output is correct