oj.uz

Submission #914814

# Submission time Handle Problem Language Result Execution time Memory
914814 2024-01-22T17:35:21 Z nima_aryan Inside information (BOI21_servers) C++17
100 / 100
 565 ms 35732 KB 
/**
 *    author:  NimaAryan
 *    created: 2024-01-22 15:04:53
**/
#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template <typename T, class C = less<>>
using indexed_set = tree<T, null_type, C, rb_tree_tag,
      tree_order_statistics_node_update>;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

struct Solver {
  int n, k;
  vector<vector<pair<int, int>>> adj;

  vector<vector<pair<int, int>>> qry1;
  vector<vector<int>> qry2;

  vector<int> siz;
  vector<bool> alive;

  vector<int> join;
  vector<int> leave;
  vector<int> reach;

  vector<int> label;

  vector<int> ans;

  Solver(int n, int k) : n(n), k(k) {
    adj.resize(n);

    qry1.resize(n);
    qry2.resize(n);

    siz.resize(n);
    alive.assign(n, true);

    join.assign(n, -1);
    leave.assign(n, -1);
    reach.assign(n, -1);

    label.resize(n);

    ans.resize(n - 1 + k);
  }

  void add_edge(int a, int b, int w) {
    adj[a].emplace_back(b, w);
    adj[b].emplace_back(a, w);
  }

  void add_query1(int a, int d, int t) {
    qry1[d].emplace_back(a, t);
  }
  void add_query2(int d, int t) {
    qry2[d].push_back(t);
  }

  void dfs(int v, int p = -1) {
    siz[v] = 1;
    for (auto [u, _] : adj[v]) {
      if (u != p && alive[u]) {
        dfs(u, v);
        siz[v] += siz[u];
      }
    }
    leave[v] = -1;
    join[v] = reach[v] = n + k;
  }
  int find_centroid(int v, int z, int p = -1) {
    for (auto [u, _] : adj[v]) {
      if (u != p && alive[u] && siz[u] > z / 2) {
        return find_centroid(u, z, v);
      }
    }
    return v;
  }

  void solve(int v = 0) {
    dfs(v);
    int c = find_centroid(v, siz[v]);

    {
      /* increasing */
      auto downward = [&](auto self, int x, int p) -> void {
        for (auto [y, z] : adj[x]) {
          if (y != p && alive[y] && reach[x] < z) {
            leave[y] = leave[x];
            reach[y] = z;
            self(self, y, x);
          }
        }
      };
      for (auto [u, w] : adj[c]) {
        if (alive[u]) {
          leave[u] = reach[u] = w;
          downward(downward, u, c);
        }
      }
    }
    {
      /* decreasing */
      auto upward = [&](auto self, int x, int w, int p) -> void {
        for (auto [y, z] : adj[x]) {
          if (y != p && alive[y] && w > z) {
            join[y] = join[x];
            self(self, y, z, x);
          }
        }
      };
      for (auto [u, w] : adj[c]) {
        if (alive[u]) {
          join[u] = w;
          upward(upward, u, w, c);
        }
      }
    }

    sort(adj[c].begin(), adj[c].end(), [&](auto p, auto q) {
      return p.second > q.second;
    });

    vector<vector<int>> subs;
    auto trav = [&](auto self, int x, int p) -> void {
      subs.back().push_back(x);
      label[x] = subs.size();
      for (auto [y, _] : adj[x]) {
        if (y != p && alive[y]) {
          self(self, y, x);
        }
      }
    };
    for (auto [u, _] : adj[c]) {
      if (alive[u]) {
        subs.emplace_back();
        trav(trav, u, c);
      }
    }

    indexed_set<int> can;
    for (auto s : subs) {
      for (int d : s) {
        for (auto [a, t] : qry1[d]) {
          if (ans[t]) {
            continue;
          }
          if (a == d) {
            ans[t] = -1;
            continue;
          }
          if (a == c) {
            ans[t] = -1 + -(join[d] >= t);
            continue;
          }
          if (label[a] == label[d]) {
            continue;
          }
          ans[t] = -1 + -(join[d] >= leave[a] || reach[a] >= t);
        }
        for (int t : qry2[d]) {
          if (join[d] < t) {
            ans[t] += can.order_of_key(t) + 1;
          }
        }
      }
      for (int x : s) {
        can.insert(reach[x]);
      }
    }

    {
      int d = c;
      for (auto [a, t] : qry1[d]) {
        if (ans[t]) {
          continue;
        }
        if (a == d) {
          ans[t] = -1;
          continue;
        }
        ans[t] = -1 + -(reach[a] >= t);
      }
      for (int t : qry2[d]) {
        ans[t] += can.order_of_key(t) + 1;
      }
    }

    alive[c] = false;
    for (auto [u, _] : adj[c]) {
      if (alive[u]) {
        solve(u);
      }
    }
  }
};

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

  int n, k;
  cin >> n >> k;

  Solver t(n, k);
  for (int i = 0; i < n - 1 + k; ++i) {
    char op;
    cin >> op;
    if (op == 'S') {
      int a, b;
      cin >> a >> b;
      --a, --b;
      t.add_edge(a, b, i);
    } else if (op == 'Q') {
      int a, d;
      cin >> a >> d;
      --a, --d;
      t.add_query1(a, d, i);
    } else {
      int d;
      cin >> d;
      --d;
      t.add_query2(d, i);
    }
  }
  t.solve();

  for (int i = 0; i < n - 1 + k; ++i) {
    int res = t.ans[i];
    if (res) {
      if (res > 0) {
        cout << res << "\n";
      } else {
        cout << (res == -1 ? "yes" : "no") << "\n";
      }
    }
  }

  return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2904 KB Output is correct
2 Correct 29 ms 4436 KB Output is correct
3 Correct 26 ms 4432 KB Output is correct
4 Correct 32 ms 4432 KB Output is correct
5 Correct 42 ms 4688 KB Output is correct
6 Correct 26 ms 4604 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2904 KB Output is correct
2 Correct 29 ms 4436 KB Output is correct
3 Correct 26 ms 4432 KB Output is correct
4 Correct 32 ms 4432 KB Output is correct
5 Correct 42 ms 4688 KB Output is correct
6 Correct 26 ms 4604 KB Output is correct
7 Correct 19 ms 3420 KB Output is correct
8 Correct 30 ms 3740 KB Output is correct
9 Correct 26 ms 3820 KB Output is correct
10 Correct 39 ms 3940 KB Output is correct
11 Correct 37 ms 3924 KB Output is correct
12 Correct 26 ms 4092 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2908 KB Output is correct
2 Correct 209 ms 32960 KB Output is correct
3 Correct 262 ms 33068 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2908 KB Output is correct
2 Correct 209 ms 32960 KB Output is correct
3 Correct 262 ms 33068 KB Output is correct
4 Correct 18 ms 3392 KB Output is correct
5 Correct 219 ms 32960 KB Output is correct
6 Correct 188 ms 30972 KB Output is correct
7 Correct 160 ms 31012 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2724 KB Output is correct
2 Correct 308 ms 26328 KB Output is correct
3 Correct 282 ms 26256 KB Output is correct
4 Correct 346 ms 31536 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2724 KB Output is correct
2 Correct 308 ms 26328 KB Output is correct
3 Correct 282 ms 26256 KB Output is correct
4 Correct 346 ms 31536 KB Output is correct
5 Correct 20 ms 3408 KB Output is correct
6 Correct 289 ms 26484 KB Output is correct
7 Correct 370 ms 31176 KB Output is correct
8 Correct 283 ms 26132 KB Output is correct
9 Correct 352 ms 26216 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2848 KB Output is correct
2 Correct 302 ms 29216 KB Output is correct
3 Correct 276 ms 22388 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2848 KB Output is correct
2 Correct 302 ms 29216 KB Output is correct
3 Correct 276 ms 22388 KB Output is correct
4 Correct 18 ms 3420 KB Output is correct
5 Correct 278 ms 29440 KB Output is correct
6 Correct 269 ms 22368 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2904 KB Output is correct
2 Correct 295 ms 26328 KB Output is correct
3 Correct 308 ms 26344 KB Output is correct
4 Correct 326 ms 31544 KB Output is correct
5 Correct 21 ms 3416 KB Output is correct
6 Correct 282 ms 29292 KB Output is correct
7 Correct 289 ms 22344 KB Output is correct
8 Correct 308 ms 23384 KB Output is correct
9 Correct 286 ms 22860 KB Output is correct
10 Correct 451 ms 26968 KB Output is correct
11 Correct 330 ms 25952 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2904 KB Output is correct
2 Correct 295 ms 26328 KB Output is correct
3 Correct 308 ms 26344 KB Output is correct
4 Correct 326 ms 31544 KB Output is correct
5 Correct 21 ms 3416 KB Output is correct
6 Correct 282 ms 29292 KB Output is correct
7 Correct 289 ms 22344 KB Output is correct
8 Correct 308 ms 23384 KB Output is correct
9 Correct 286 ms 22860 KB Output is correct
10 Correct 451 ms 26968 KB Output is correct
11 Correct 330 ms 25952 KB Output is correct
12 Correct 19 ms 3352 KB Output is correct
13 Correct 259 ms 26492 KB Output is correct
14 Correct 325 ms 31288 KB Output is correct
15 Correct 234 ms 25956 KB Output is correct
16 Correct 256 ms 26164 KB Output is correct
17 Correct 20 ms 3276 KB Output is correct
18 Correct 285 ms 29472 KB Output is correct
19 Correct 231 ms 22304 KB Output is correct
20 Correct 269 ms 23424 KB Output is correct
21 Correct 284 ms 23404 KB Output is correct
22 Correct 342 ms 26208 KB Output is correct
23 Correct 565 ms 28344 KB Output is correct
24 Correct 515 ms 28048 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2908 KB Output is correct
2 Correct 29 ms 4560 KB Output is correct
3 Correct 25 ms 4436 KB Output is correct
4 Correct 36 ms 4424 KB Output is correct
5 Correct 32 ms 4688 KB Output is correct
6 Correct 26 ms 4696 KB Output is correct
7 Correct 17 ms 3416 KB Output is correct
8 Correct 217 ms 32976 KB Output is correct
9 Correct 219 ms 33052 KB Output is correct
10 Correct 20 ms 3404 KB Output is correct
11 Correct 298 ms 26248 KB Output is correct
12 Correct 298 ms 26120 KB Output is correct
13 Correct 315 ms 31588 KB Output is correct
14 Correct 19 ms 3416 KB Output is correct
15 Correct 289 ms 29500 KB Output is correct
16 Correct 227 ms 22520 KB Output is correct
17 Correct 249 ms 23324 KB Output is correct
18 Correct 285 ms 23244 KB Output is correct
19 Correct 381 ms 26880 KB Output is correct
20 Correct 395 ms 25632 KB Output is correct
21 Correct 223 ms 35732 KB Output is correct
22 Correct 231 ms 31076 KB Output is correct
23 Correct 209 ms 23384 KB Output is correct
24 Correct 210 ms 23344 KB Output is correct
25 Correct 342 ms 30884 KB Output is correct
26 Correct 245 ms 21680 KB Output is correct
27 Correct 208 ms 21576 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2908 KB Output is correct
2 Correct 29 ms 4560 KB Output is correct
3 Correct 25 ms 4436 KB Output is correct
4 Correct 36 ms 4424 KB Output is correct
5 Correct 32 ms 4688 KB Output is correct
6 Correct 26 ms 4696 KB Output is correct
7 Correct 17 ms 3416 KB Output is correct
8 Correct 217 ms 32976 KB Output is correct
9 Correct 219 ms 33052 KB Output is correct
10 Correct 20 ms 3404 KB Output is correct
11 Correct 298 ms 26248 KB Output is correct
12 Correct 298 ms 26120 KB Output is correct
13 Correct 315 ms 31588 KB Output is correct
14 Correct 19 ms 3416 KB Output is correct
15 Correct 289 ms 29500 KB Output is correct
16 Correct 227 ms 22520 KB Output is correct
17 Correct 249 ms 23324 KB Output is correct
18 Correct 285 ms 23244 KB Output is correct
19 Correct 381 ms 26880 KB Output is correct
20 Correct 395 ms 25632 KB Output is correct
21 Correct 223 ms 35732 KB Output is correct
22 Correct 231 ms 31076 KB Output is correct
23 Correct 209 ms 23384 KB Output is correct
24 Correct 210 ms 23344 KB Output is correct
25 Correct 342 ms 30884 KB Output is correct
26 Correct 245 ms 21680 KB Output is correct
27 Correct 208 ms 21576 KB Output is correct
28 Correct 21 ms 3412 KB Output is correct
29 Correct 31 ms 3916 KB Output is correct
30 Correct 25 ms 3920 KB Output is correct
31 Correct 31 ms 3920 KB Output is correct
32 Correct 31 ms 4048 KB Output is correct
33 Correct 27 ms 4188 KB Output is correct
34 Correct 17 ms 3420 KB Output is correct
35 Correct 188 ms 32760 KB Output is correct
36 Correct 176 ms 30836 KB Output is correct
37 Correct 158 ms 30912 KB Output is correct
38 Correct 18 ms 3408 KB Output is correct
39 Correct 283 ms 26748 KB Output is correct
40 Correct 353 ms 31116 KB Output is correct
41 Correct 268 ms 26348 KB Output is correct
42 Correct 245 ms 25960 KB Output is correct
43 Correct 18 ms 3420 KB Output is correct
44 Correct 283 ms 29260 KB Output is correct
45 Correct 227 ms 22492 KB Output is correct
46 Correct 262 ms 23428 KB Output is correct
47 Correct 281 ms 23588 KB Output is correct
48 Correct 358 ms 26256 KB Output is correct
49 Correct 520 ms 28088 KB Output is correct
50 Correct 485 ms 27976 KB Output is correct
51 Correct 192 ms 34236 KB Output is correct
52 Correct 173 ms 31472 KB Output is correct
53 Correct 197 ms 31376 KB Output is correct
54 Correct 159 ms 31408 KB Output is correct
55 Correct 178 ms 32052 KB Output is correct
56 Correct 193 ms 22388 KB Output is correct
57 Correct 277 ms 27784 KB Output is correct
58 Correct 302 ms 22200 KB Output is correct
59 Correct 222 ms 21508 KB Output is correct