oj.uz

Submission #400958

# Submission time Handle Problem Language Result Execution time Memory
400958 2021-05-08T22:17:53 Z Hegdahl Inside information (BOI21_servers) C++17
100 / 100
 2713 ms 280196 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ar array

using namespace __gnu_pbds;
using namespace std;

using iset = tree<ar<int, 2>, null_type, less<ar<int, 2>>, rb_tree_tag, tree_order_statistics_node_update>;

const int mxN = 120'000;
const int INF = 1e9;

vector<ar<int, 2>> g[mxN];

int cut[mxN], sz[mxN];

int dfs1(int cur, int prv) {
  sz[cur] = 1;
  for (auto [nxt, t] : g[cur]) {
    if (cut[nxt]) continue;
    if (nxt == prv) continue;
    sz[cur] += dfs1(nxt, cur);
  }
  return sz[cur];
}

vector<int> kids[mxN];
int find_centroid(int cur, int prv, int total) {
  for (auto [nxt, t] : g[cur]) {
    if (cut[nxt]) continue;
    if (nxt == prv) continue;
    if (2*sz[nxt] > total) return find_centroid(nxt, cur, total);
  }

  // this is centroid

  cut[cur] = 1;
  if (prv != -1 && !cut[prv])
    dfs1(prv, -1);

  for (auto [nxt, t] : g[cur]) {
    if (cut[nxt]) continue;
    kids[cur].push_back(find_centroid(nxt, -1, sz[nxt]));
  }

  return cur;
}

int clvl[mxN];
vector<int> cent_anc[mxN];

iset branches_start[mxN];

void set_anc(int anc, int cur, int prv) {
  cent_anc[cur].push_back(anc);

  for (auto [nxt, t] : g[cur]) {
    if (cut[nxt]) continue;
    if (nxt == prv) continue;
    set_anc(anc, nxt, cur);
  }
}

gp_hash_table<int, int> out_ws[mxN], in_ws[mxN], path_end[mxN];

void init_reach_out(int root, int bw, int cur, int prv, int w) {
  out_ws[root][cur] = bw;
  path_end[root][cur] = w;

  for (auto [nxt, t] : g[cur]) {
    if (cut[nxt]) continue;
    if (nxt == prv) continue;
    if (t < w) continue;
    init_reach_out(root, bw, nxt, cur, t);
  }
}

void init_reach_in(int root, int bw, int cur, int prv, int w) {
  in_ws[root][cur] = bw;

  for (auto [nxt, t] : g[cur]) {
    if (cut[nxt]) continue;
    if (nxt == prv) continue;
    if (t > w) continue;
    init_reach_in(root, bw, nxt, cur, t);
  }
}

void init_centroid(int cur, int d) {
  clvl[cur] = d;
  for (int nxt : kids[cur])
    init_centroid(nxt, d+1);

  cent_anc[cur].push_back(cur);
  for (auto [nxt, t] : g[cur]) {
    if (cut[nxt]) continue;
    set_anc(cur, nxt, -1);
  }

  cut[cur] = 0;

  out_ws[cur][cur] = INF;
  in_ws[cur][cur] = -INF;
  path_end[cur][cur] = -INF;

  for (auto [nxt, t] : g[cur]) {
    if (cut[nxt]) continue;
    init_reach_out(cur, t, nxt, cur, t);
    init_reach_in(cur, t, nxt, cur, t);
  }

}

bool qry(int i, int j, int t) {
  int ci = 0;
  int cj = 0;

  while (cent_anc[i][ci] != cent_anc[j][cj]) {
    if (clvl[cent_anc[i][ci]] > clvl[cent_anc[j][cj]]) ++ci;
    else if (clvl[cent_anc[j][cj]] > clvl[cent_anc[i][ci]]) ++cj;
    else ++ci, ++cj;
  }

  int lca = cent_anc[i][ci];

  auto in_it = in_ws[lca].find(j);
  auto out_it = out_ws[lca].find(i);
  if (in_it == in_ws[lca].end()) return false;
  if (out_it == out_ws[lca].end()) return false;

  if (in_it->second > t) return false;
  if (in_it->second > out_it->second) return false;
  if (path_end[lca][i] > t) return false;

  return true;
}

int count_reachable(int i, int hi) {
  int ans = 0;

  for (int root : cent_anc[i]) {
    auto reach_it = in_ws[root].find(i);
    if (reach_it == in_ws[root].end()) continue;
    int lo = reach_it->second;
    if (lo > hi) continue;
    
    ++ans;

    int here = (int)branches_start[root].size();
    if (here) {
      if (lo >= 0) here -= (int)branches_start[root].order_of_key({lo, INF});
      if (here < 0) here = 0;
    }
    ans += here;
  }

  return ans;
}

int brute_reachable(int i, int t, int n) {
  int ans = 0;
  for (int j = 0; j < n; ++j)
    ans += qry(j, i, t);
  return ans;
}

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

  int n, q; cin >> n >> q;

  vector<ar<int, 3>> qs;
  vector<ar<int, 2>> cs;

  for (int t = 0; t < n+q-1; ++t) {
    char c; cin >> c;
    if (c == 'S') {
      int i, j; cin >> i >> j; --i, --j;
      g[i].push_back({j, t});
      g[j].push_back({i, t});
    } else if (c == 'Q') {
      int i, j; cin >> i >> j; --i, --j;
      qs.push_back({t, i, j});
    } else if (c == 'C') {
      int i; cin >> i; --i;
      cs.push_back({t, i});
    } else assert(0);
  }

  dfs1(0, -1);
  int root = find_centroid(0, -1, sz[0]);
  for (int i = 0; i < n; ++i)
    assert(cut[i]);

  init_centroid(root, 0);
  for (int i = 0; i < n; ++i)
    assert(!cut[i]);

  vector<pair<int, string>> ans; ans.reserve(q);

  for (auto [t, i, j] : qs)
    ans.push_back({t, qry(i, j, t)?"yes":"no"});

  vector<ar<int, 4>> upd_q;

  for (int i = 0; i < n; ++i) {
    for (int rt : cent_anc[i]) {
      if (i == rt) continue;
      auto out_it = out_ws[rt].find(i);
      if (out_it == out_ws[rt].end()) continue;
      int w_start = out_it->second;
      int w_end = path_end[rt][i];
      upd_q.push_back({w_end, w_start, rt, i});
    }
  }

  int upd_i = 0;
  sort(upd_q.begin(), upd_q.end());

  for (auto [t, i] : cs) {
    while (upd_i < (int)upd_q.size() && upd_q[upd_i][0] <= t) {
      auto [ut, w, rt, nd] = upd_q[upd_i++];
      branches_start[rt].insert({w, nd});
    }

    ans.push_back({t, to_string(count_reachable(i, t))});
  }

  sort(ans.begin(), ans.end());

  for (auto &[t, s] : ans)
    cout << s << '\n';
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 137 ms 102680 KB Output is correct
2 Correct 163 ms 103724 KB Output is correct
3 Correct 157 ms 103868 KB Output is correct
4 Correct 165 ms 104112 KB Output is correct
5 Correct 160 ms 103932 KB Output is correct
6 Correct 153 ms 103340 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 137 ms 102680 KB Output is correct
2 Correct 163 ms 103724 KB Output is correct
3 Correct 157 ms 103868 KB Output is correct
4 Correct 165 ms 104112 KB Output is correct
5 Correct 160 ms 103932 KB Output is correct
6 Correct 153 ms 103340 KB Output is correct
7 Correct 150 ms 102604 KB Output is correct
8 Correct 199 ms 104812 KB Output is correct
9 Correct 190 ms 105036 KB Output is correct
10 Correct 204 ms 104976 KB Output is correct
11 Correct 200 ms 104900 KB Output is correct
12 Correct 183 ms 104540 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 135 ms 102684 KB Output is correct
2 Correct 386 ms 126144 KB Output is correct
3 Correct 412 ms 126136 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 135 ms 102684 KB Output is correct
2 Correct 386 ms 126144 KB Output is correct
3 Correct 412 ms 126136 KB Output is correct
4 Correct 149 ms 102592 KB Output is correct
5 Correct 497 ms 134304 KB Output is correct
6 Correct 457 ms 133132 KB Output is correct
7 Correct 489 ms 133272 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 102620 KB Output is correct
2 Correct 635 ms 149364 KB Output is correct
3 Correct 630 ms 149616 KB Output is correct
4 Correct 806 ms 228576 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 102620 KB Output is correct
2 Correct 635 ms 149364 KB Output is correct
3 Correct 630 ms 149616 KB Output is correct
4 Correct 806 ms 228576 KB Output is correct
5 Correct 148 ms 102612 KB Output is correct
6 Correct 793 ms 157752 KB Output is correct
7 Correct 1357 ms 280060 KB Output is correct
8 Correct 833 ms 156968 KB Output is correct
9 Correct 824 ms 156968 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 102676 KB Output is correct
2 Correct 2129 ms 195296 KB Output is correct
3 Correct 590 ms 135788 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 102676 KB Output is correct
2 Correct 2129 ms 195296 KB Output is correct
3 Correct 590 ms 135788 KB Output is correct
4 Correct 147 ms 102652 KB Output is correct
5 Correct 2711 ms 244028 KB Output is correct
6 Correct 765 ms 149732 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 138 ms 102636 KB Output is correct
2 Correct 626 ms 149564 KB Output is correct
3 Correct 630 ms 149392 KB Output is correct
4 Correct 808 ms 228636 KB Output is correct
5 Correct 142 ms 102664 KB Output is correct
6 Correct 2109 ms 195312 KB Output is correct
7 Correct 583 ms 135840 KB Output is correct
8 Correct 772 ms 142704 KB Output is correct
9 Correct 799 ms 142656 KB Output is correct
10 Correct 1168 ms 187992 KB Output is correct
11 Correct 1140 ms 187636 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 138 ms 102636 KB Output is correct
2 Correct 626 ms 149564 KB Output is correct
3 Correct 630 ms 149392 KB Output is correct
4 Correct 808 ms 228636 KB Output is correct
5 Correct 142 ms 102664 KB Output is correct
6 Correct 2109 ms 195312 KB Output is correct
7 Correct 583 ms 135840 KB Output is correct
8 Correct 772 ms 142704 KB Output is correct
9 Correct 799 ms 142656 KB Output is correct
10 Correct 1168 ms 187992 KB Output is correct
11 Correct 1140 ms 187636 KB Output is correct
12 Correct 149 ms 102556 KB Output is correct
13 Correct 779 ms 157564 KB Output is correct
14 Correct 1356 ms 280160 KB Output is correct
15 Correct 830 ms 157096 KB Output is correct
16 Correct 811 ms 156940 KB Output is correct
17 Correct 149 ms 103480 KB Output is correct
18 Correct 2713 ms 243932 KB Output is correct
19 Correct 751 ms 149716 KB Output is correct
20 Correct 974 ms 153924 KB Output is correct
21 Correct 976 ms 154272 KB Output is correct
22 Correct 1617 ms 215008 KB Output is correct
23 Correct 2098 ms 257068 KB Output is correct
24 Correct 1807 ms 250900 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 136 ms 102628 KB Output is correct
2 Correct 163 ms 103652 KB Output is correct
3 Correct 157 ms 103864 KB Output is correct
4 Correct 166 ms 104036 KB Output is correct
5 Correct 162 ms 104000 KB Output is correct
6 Correct 152 ms 103364 KB Output is correct
7 Correct 139 ms 102708 KB Output is correct
8 Correct 375 ms 126068 KB Output is correct
9 Correct 378 ms 126160 KB Output is correct
10 Correct 135 ms 102704 KB Output is correct
11 Correct 629 ms 149404 KB Output is correct
12 Correct 622 ms 149488 KB Output is correct
13 Correct 811 ms 228644 KB Output is correct
14 Correct 139 ms 102616 KB Output is correct
15 Correct 2117 ms 195292 KB Output is correct
16 Correct 578 ms 135792 KB Output is correct
17 Correct 783 ms 142600 KB Output is correct
18 Correct 798 ms 142624 KB Output is correct
19 Correct 1173 ms 187872 KB Output is correct
20 Correct 1165 ms 187380 KB Output is correct
21 Correct 422 ms 132612 KB Output is correct
22 Correct 431 ms 134144 KB Output is correct
23 Correct 585 ms 140780 KB Output is correct
24 Correct 568 ms 141036 KB Output is correct
25 Correct 753 ms 144348 KB Output is correct
26 Correct 836 ms 155092 KB Output is correct
27 Correct 839 ms 155276 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 136 ms 102628 KB Output is correct
2 Correct 163 ms 103652 KB Output is correct
3 Correct 157 ms 103864 KB Output is correct
4 Correct 166 ms 104036 KB Output is correct
5 Correct 162 ms 104000 KB Output is correct
6 Correct 152 ms 103364 KB Output is correct
7 Correct 139 ms 102708 KB Output is correct
8 Correct 375 ms 126068 KB Output is correct
9 Correct 378 ms 126160 KB Output is correct
10 Correct 135 ms 102704 KB Output is correct
11 Correct 629 ms 149404 KB Output is correct
12 Correct 622 ms 149488 KB Output is correct
13 Correct 811 ms 228644 KB Output is correct
14 Correct 139 ms 102616 KB Output is correct
15 Correct 2117 ms 195292 KB Output is correct
16 Correct 578 ms 135792 KB Output is correct
17 Correct 783 ms 142600 KB Output is correct
18 Correct 798 ms 142624 KB Output is correct
19 Correct 1173 ms 187872 KB Output is correct
20 Correct 1165 ms 187380 KB Output is correct
21 Correct 422 ms 132612 KB Output is correct
22 Correct 431 ms 134144 KB Output is correct
23 Correct 585 ms 140780 KB Output is correct
24 Correct 568 ms 141036 KB Output is correct
25 Correct 753 ms 144348 KB Output is correct
26 Correct 836 ms 155092 KB Output is correct
27 Correct 839 ms 155276 KB Output is correct
28 Correct 150 ms 102592 KB Output is correct
29 Correct 196 ms 104740 KB Output is correct
30 Correct 192 ms 105036 KB Output is correct
31 Correct 204 ms 104936 KB Output is correct
32 Correct 205 ms 104964 KB Output is correct
33 Correct 184 ms 104452 KB Output is correct
34 Correct 156 ms 103520 KB Output is correct
35 Correct 483 ms 134272 KB Output is correct
36 Correct 452 ms 133128 KB Output is correct
37 Correct 491 ms 133260 KB Output is correct
38 Correct 148 ms 103508 KB Output is correct
39 Correct 785 ms 157648 KB Output is correct
40 Correct 1362 ms 280196 KB Output is correct
41 Correct 828 ms 156968 KB Output is correct
42 Correct 824 ms 156848 KB Output is correct
43 Correct 149 ms 103536 KB Output is correct
44 Correct 2694 ms 244096 KB Output is correct
45 Correct 758 ms 149688 KB Output is correct
46 Correct 972 ms 153868 KB Output is correct
47 Correct 980 ms 154040 KB Output is correct
48 Correct 1622 ms 214884 KB Output is correct
49 Correct 2124 ms 257004 KB Output is correct
50 Correct 1775 ms 251004 KB Output is correct
51 Correct 520 ms 141728 KB Output is correct
52 Correct 459 ms 134172 KB Output is correct
53 Correct 430 ms 133592 KB Output is correct
54 Correct 422 ms 134312 KB Output is correct
55 Correct 426 ms 135836 KB Output is correct
56 Correct 747 ms 154264 KB Output is correct
57 Correct 835 ms 149496 KB Output is correct
58 Correct 1099 ms 159284 KB Output is correct
59 Correct 885 ms 163524 KB Output is correct