oj.uz

Submission #666764

# Submission time Handle Problem Language Result Execution time Memory
666764 2022-11-29T15:55:08 Z MilosMilutinovic Inside information (BOI21_servers) C++14
100 / 100
 564 ms 44116 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  q += n - 1;
  vector<vector<pair<int, int>>> g(n);
  vector<char> op(q);
  vector<int> x(q);
  vector<int> y(q);
  for (int i = 0; i < q; i++) {
    string foo;
    cin >> foo;
    op[i] = foo[0];
    if (op[i] == 'S') {
      cin >> x[i] >> y[i];
      --x[i]; --y[i];
      g[x[i]].emplace_back(y[i], i);
      g[y[i]].emplace_back(x[i], i);
    }
    if (op[i] == 'Q') {
      cin >> x[i] >> y[i];
      --x[i]; --y[i];
    }
    if (op[i] == 'C') {
      cin >> x[i];
      --x[i];
    }
  }
  vector<vector<int>> qs(n);
  for (int i = 0; i < q; i++) {
    if (op[i] == 'C') {
      qs[x[i]].push_back(i);
    }
  }
  for (int i = 0; i < n; i++) {
    sort(g[i].begin(), g[i].end(), [&](pair<int, int> a, pair<int, int> b) {
      return a.second > b.second;
    });
  }
  vector<bool> was(n);
  vector<int> sz(n);
  function<void(int, int)> Find_sz = [&](int v, int pv) {
    sz[v] = 1;
    for (auto& p : g[v]) {
      int to = p.first;
      if (!was[to] && to != pv) {
        Find_sz(to, v);
        sz[v] += sz[to];
      }
    }
  };
  function<int(int, int, int)> Find_cen = [&](int v, int pv, int n) {
    for (auto& p : g[v]) {
      int to = p.first;
      if (!was[to] && to != pv && sz[to] * 2 >= n) {
        return Find_cen(to, v, n);
      }
    }
    return v;
  };
  vector<int> qv;
  vector<int> fenw(q + 1);
  auto Modify = [&](int x, int v) {
    for (x++; x <= q; x += x & -x) {
      fenw[x] += v;
    }
  };
  auto Query = [&](int x) {
    int r = 0;
    for (x++; x > 0; x -= x & -x) {
      r += fenw[x];
    }
    return r;
  };
  vector<int> ans(q);
  function<void(int, int, int, int, bool, bool)> Go = [&](int v, int pv, int prv_w, int fir, bool inc, bool dec) {
    if (dec) {
      for (auto& p : qs[v]) {
        ans[p] += Query(p) + (fir <= p);
      }
    }
    if (inc) {
      qv.push_back(prv_w);
    }
    for (auto& p : g[v]) {
      int to = p.first;
      int w = p.second;
      if (!was[to] && to != pv) {
        Go(to, v, w, fir, (inc & (w > prv_w)), (dec & (w < prv_w)));
      }
    }
  };
  function<void(int, int)> Decompose = [&](int v, int pv) {
    Find_sz(v, v);
    v = Find_cen(v, v, sz[v]);
    was[v] = true;
    vector<int> rv;
    for (auto& p : g[v]) {
      int to = p.first;
      int w = p.second;
      if (!was[to]) {
        Go(to, v, w, w, 1, 1);
        for (auto& p : qv) {
          Modify(p, +1);
          rv.push_back(p);
        }
        qv.clear();
      }
    }   
    for (auto& p : qs[v]) {
      ans[p] += Query(p);
    }
    for (auto& p : rv) {
      Modify(p, -1);
    }
    for (auto& p : g[v]) {
      int to = p.first;
      if (!was[to] && to != pv) {
        Decompose(to, v);
      }
    }
  };
  Decompose(0, -1);
  const int L = 20;
  vector<int> inc_up(n);
  vector<int> dec_up(n);
  vector<int> dep(n);
  vector<int> up(n);
  vector<vector<int>> pr(L, vector<int>(n));
  function<void(int, int, int)> Dfs = [&](int v, int pv, int prv_w) {
    pr[0][v] = pv;
    up[v] = prv_w;
    for (auto& p : g[v]) {
      int to = p.first;
      int w = p.second;
      if (to == pv) {
        continue;
      }
      dep[to] = dep[v] + 1;
      if (prv_w == -1) {
        inc_up[to] = 0;
        dec_up[to] = 0;        
      } else if (prv_w > w) {
        inc_up[to] = inc_up[v];
        dec_up[to] = dep[v];
      } else {
        inc_up[to] = dep[v];
        dec_up[to] = dec_up[v];
      }
      Dfs(to, v, w);
    }
  };
  Dfs(0, 0, -1);
  for (int j = 1; j < L; j++) {
    for (int i = 0; i < n; i++) {
      pr[j][i] = pr[j - 1][pr[j - 1][i]];
    }
  }
  auto LCA = [&](int x, int y) {
    if (dep[x] < dep[y]) {
      swap(x, y);
    }
    for (int i = L - 1; i >= 0; i--) {
      if (dep[pr[i][x]] >= dep[y]) {
        x = pr[i][x];
      }
    }
    if (x == y) {
      return x;
    }    
    for (int i = L - 1; i >= 0; i--) {
      if (pr[i][x] != pr[i][y]) {
        x = pr[i][x];
        y = pr[i][y];
      }
    }
    return pr[0][x];
  };
  auto GoUp = [&](int x, int k) {
    for (int i = L - 1; i >= 0; i--) {
      if (k >> i & 1) {
        x = pr[i][x];
      }
    }
    return x;
  };
  for (int i = 0; i < q; i++) {
    if (op[i] == 'Q') {
      swap(x[i], y[i]);
      int lca = LCA(x[i], y[i]);
      bool is_inc = (inc_up[x[i]] <= dep[lca] && dec_up[y[i]] <= dep[lca]);
      is_inc = (is_inc & (x[i] == lca || y[i] == lca || up[GoUp(x[i], dep[x[i]] - dep[lca] - 1)] < up[GoUp(y[i], dep[y[i]] - dep[lca] - 1)]));
      if (x[i] != lca) {
        is_inc = (is_inc && up[GoUp(x[i], dep[x[i]] - dep[lca] - 1)] < i);
      }
      if (y[i] != lca) {
        is_inc = (is_inc && up[y[i]] < i);
      }
      cout << (is_inc ? "yes" : "no") << '\n';
    }
    if (op[i] == 'C') {
      cout << ans[i] + 1 << '\n';
    }
  }
  return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2636 KB Output is correct
2 Correct 67 ms 4844 KB Output is correct
3 Correct 66 ms 4920 KB Output is correct
4 Correct 76 ms 5044 KB Output is correct
5 Correct 60 ms 5204 KB Output is correct
6 Correct 68 ms 4980 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2636 KB Output is correct
2 Correct 67 ms 4844 KB Output is correct
3 Correct 66 ms 4920 KB Output is correct
4 Correct 76 ms 5044 KB Output is correct
5 Correct 60 ms 5204 KB Output is correct
6 Correct 68 ms 4980 KB Output is correct
7 Correct 46 ms 3532 KB Output is correct
8 Correct 60 ms 4988 KB Output is correct
9 Correct 54 ms 5028 KB Output is correct
10 Correct 59 ms 5156 KB Output is correct
11 Correct 53 ms 5356 KB Output is correct
12 Correct 53 ms 5012 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 2636 KB Output is correct
2 Correct 269 ms 30140 KB Output is correct
3 Correct 270 ms 30160 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 2636 KB Output is correct
2 Correct 269 ms 30140 KB Output is correct
3 Correct 270 ms 30160 KB Output is correct
4 Correct 49 ms 3612 KB Output is correct
5 Correct 250 ms 30216 KB Output is correct
6 Correct 101 ms 29720 KB Output is correct
7 Correct 116 ms 30156 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2592 KB Output is correct
2 Correct 428 ms 42384 KB Output is correct
3 Correct 448 ms 42500 KB Output is correct
4 Correct 293 ms 42652 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2592 KB Output is correct
2 Correct 428 ms 42384 KB Output is correct
3 Correct 448 ms 42500 KB Output is correct
4 Correct 293 ms 42652 KB Output is correct
5 Correct 40 ms 3684 KB Output is correct
6 Correct 373 ms 43428 KB Output is correct
7 Correct 290 ms 44116 KB Output is correct
8 Correct 307 ms 43804 KB Output is correct
9 Correct 304 ms 43796 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2664 KB Output is correct
2 Correct 313 ms 30500 KB Output is correct
3 Correct 351 ms 30668 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2664 KB Output is correct
2 Correct 313 ms 30500 KB Output is correct
3 Correct 351 ms 30668 KB Output is correct
4 Correct 44 ms 3548 KB Output is correct
5 Correct 296 ms 31700 KB Output is correct
6 Correct 335 ms 31380 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2688 KB Output is correct
2 Correct 452 ms 42400 KB Output is correct
3 Correct 417 ms 42388 KB Output is correct
4 Correct 287 ms 42716 KB Output is correct
5 Correct 43 ms 3568 KB Output is correct
6 Correct 332 ms 30528 KB Output is correct
7 Correct 361 ms 30616 KB Output is correct
8 Correct 370 ms 31180 KB Output is correct
9 Correct 448 ms 31076 KB Output is correct
10 Correct 499 ms 37236 KB Output is correct
11 Correct 564 ms 36328 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2688 KB Output is correct
2 Correct 452 ms 42400 KB Output is correct
3 Correct 417 ms 42388 KB Output is correct
4 Correct 287 ms 42716 KB Output is correct
5 Correct 43 ms 3568 KB Output is correct
6 Correct 332 ms 30528 KB Output is correct
7 Correct 361 ms 30616 KB Output is correct
8 Correct 370 ms 31180 KB Output is correct
9 Correct 448 ms 31076 KB Output is correct
10 Correct 499 ms 37236 KB Output is correct
11 Correct 564 ms 36328 KB Output is correct
12 Correct 41 ms 3540 KB Output is correct
13 Correct 390 ms 43516 KB Output is correct
14 Correct 337 ms 44056 KB Output is correct
15 Correct 343 ms 43908 KB Output is correct
16 Correct 378 ms 43836 KB Output is correct
17 Correct 42 ms 3532 KB Output is correct
18 Correct 317 ms 31656 KB Output is correct
19 Correct 317 ms 31380 KB Output is correct
20 Correct 310 ms 32224 KB Output is correct
21 Correct 377 ms 32164 KB Output is correct
22 Correct 409 ms 35860 KB Output is correct
23 Correct 446 ms 37164 KB Output is correct
24 Correct 464 ms 36108 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2608 KB Output is correct
2 Correct 67 ms 4824 KB Output is correct
3 Correct 75 ms 4976 KB Output is correct
4 Correct 72 ms 4952 KB Output is correct
5 Correct 59 ms 5220 KB Output is correct
6 Correct 68 ms 4872 KB Output is correct
7 Correct 48 ms 3552 KB Output is correct
8 Correct 280 ms 30144 KB Output is correct
9 Correct 272 ms 30056 KB Output is correct
10 Correct 39 ms 3552 KB Output is correct
11 Correct 410 ms 42404 KB Output is correct
12 Correct 452 ms 42484 KB Output is correct
13 Correct 284 ms 42696 KB Output is correct
14 Correct 44 ms 3548 KB Output is correct
15 Correct 329 ms 30644 KB Output is correct
16 Correct 336 ms 30620 KB Output is correct
17 Correct 384 ms 31308 KB Output is correct
18 Correct 392 ms 31068 KB Output is correct
19 Correct 451 ms 37196 KB Output is correct
20 Correct 488 ms 36348 KB Output is correct
21 Correct 275 ms 30772 KB Output is correct
22 Correct 282 ms 30604 KB Output is correct
23 Correct 327 ms 30820 KB Output is correct
24 Correct 328 ms 30796 KB Output is correct
25 Correct 435 ms 37504 KB Output is correct
26 Correct 308 ms 30128 KB Output is correct
27 Correct 269 ms 30272 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 2608 KB Output is correct
2 Correct 67 ms 4824 KB Output is correct
3 Correct 75 ms 4976 KB Output is correct
4 Correct 72 ms 4952 KB Output is correct
5 Correct 59 ms 5220 KB Output is correct
6 Correct 68 ms 4872 KB Output is correct
7 Correct 48 ms 3552 KB Output is correct
8 Correct 280 ms 30144 KB Output is correct
9 Correct 272 ms 30056 KB Output is correct
10 Correct 39 ms 3552 KB Output is correct
11 Correct 410 ms 42404 KB Output is correct
12 Correct 452 ms 42484 KB Output is correct
13 Correct 284 ms 42696 KB Output is correct
14 Correct 44 ms 3548 KB Output is correct
15 Correct 329 ms 30644 KB Output is correct
16 Correct 336 ms 30620 KB Output is correct
17 Correct 384 ms 31308 KB Output is correct
18 Correct 392 ms 31068 KB Output is correct
19 Correct 451 ms 37196 KB Output is correct
20 Correct 488 ms 36348 KB Output is correct
21 Correct 275 ms 30772 KB Output is correct
22 Correct 282 ms 30604 KB Output is correct
23 Correct 327 ms 30820 KB Output is correct
24 Correct 328 ms 30796 KB Output is correct
25 Correct 435 ms 37504 KB Output is correct
26 Correct 308 ms 30128 KB Output is correct
27 Correct 269 ms 30272 KB Output is correct
28 Correct 46 ms 3540 KB Output is correct
29 Correct 58 ms 4988 KB Output is correct
30 Correct 53 ms 4972 KB Output is correct
31 Correct 59 ms 5060 KB Output is correct
32 Correct 53 ms 5452 KB Output is correct
33 Correct 51 ms 5012 KB Output is correct
34 Correct 48 ms 3592 KB Output is correct
35 Correct 266 ms 30192 KB Output is correct
36 Correct 102 ms 29688 KB Output is correct
37 Correct 109 ms 30132 KB Output is correct
38 Correct 38 ms 3544 KB Output is correct
39 Correct 389 ms 43440 KB Output is correct
40 Correct 283 ms 44020 KB Output is correct
41 Correct 313 ms 43936 KB Output is correct
42 Correct 302 ms 43904 KB Output is correct
43 Correct 42 ms 3532 KB Output is correct
44 Correct 296 ms 31788 KB Output is correct
45 Correct 331 ms 31300 KB Output is correct
46 Correct 340 ms 32156 KB Output is correct
47 Correct 332 ms 32216 KB Output is correct
48 Correct 389 ms 35884 KB Output is correct
49 Correct 467 ms 37200 KB Output is correct
50 Correct 445 ms 36272 KB Output is correct
51 Correct 125 ms 31648 KB Output is correct
52 Correct 119 ms 30984 KB Output is correct
53 Correct 107 ms 30472 KB Output is correct
54 Correct 112 ms 30944 KB Output is correct
55 Correct 131 ms 30340 KB Output is correct
56 Correct 275 ms 30872 KB Output is correct
57 Correct 271 ms 37428 KB Output is correct
58 Correct 333 ms 31632 KB Output is correct
59 Correct 272 ms 30404 KB Output is correct