oj.uz

Submission #914795

# Submission time Handle Problem Language Result Execution time Memory
914795 2024-01-22T17:13:39 Z nima_aryan Inside information (BOI21_servers) C++17
100 / 100
 803 ms 35920 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;
  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> ans;

  Solver(int n, int k) : n(n) {
    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);

    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];
      }
    }
    join[v] = leave[v] = reach[v] = -1;
  }
  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 trav = [&](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;
          trav(trav, u, c);
        }
      }
    }
    {
      /* decreasing */
      auto trav = [&](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;
          trav(trav, u, w, c);
        }
      }
    }

    indexed_set<int> can;
    set<int> comp;
    auto trav = [&](auto self, int x, int p) -> void {
      comp.insert(x);
      for (auto [y, _] : adj[x]) {
        if (y != p && alive[y]) {
          self(self, y, x);
        }
      }
    };

    sort(adj[c].begin(), adj[c].end(), [&](auto p, auto q) {
      return p.second > q.second;
    });
    for (auto [u, _] : adj[c]) {
      if (alive[u]) {
        comp.clear();
        trav(trav, u, c);

        for (int d : comp) {
          for (auto [a, t] : qry1[d]) {
            if (comp.count(a)) {
              continue;
            }
            if (ans[t]) {
              continue;
            }
            if (a == d) {
              ans[t] = -1;
              continue;
            }
            if (a == c) {
              if (join[d] != -1 && join[d] < t) {
                ans[t] = -1;
              } else {
                ans[t] = -2;
              }
              continue;
            }
            if (join[d] != -1 && leave[a] != -1 && join[d] < leave[a] &&
                reach[a] != -1 && reach[a] < t) {
              ans[t] = -1;
            } else {
              ans[t] = -2;
            }
          }
          for (int t : qry2[d]) {
            if (join[d] != -1 && join[d] < t) {
              ans[t] += can.order_of_key(t) + 1;
            }
          }
        }
        for (int x : comp) {
          if (reach[x] != -1) {
            can.insert(reach[x]);
          }
        }
      }
    }

    {
      int d = c;
      for (auto [a, t] : qry1[d]) {
        if (ans[t]) {
          continue;
        }
        if (a == d) {
          ans[t] = -1;
          continue;
        }
        if (reach[a] != -1 && reach[a] < t) {
          ans[t] = -1;
        } else {
          ans[t] = -2;
        }
      }
      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 2896 KB Output is correct
2 Correct 52 ms 4348 KB Output is correct
3 Correct 35 ms 4176 KB Output is correct
4 Correct 74 ms 4408 KB Output is correct
5 Correct 52 ms 4432 KB Output is correct
6 Correct 30 ms 4432 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2896 KB Output is correct
2 Correct 52 ms 4348 KB Output is correct
3 Correct 35 ms 4176 KB Output is correct
4 Correct 74 ms 4408 KB Output is correct
5 Correct 52 ms 4432 KB Output is correct
6 Correct 30 ms 4432 KB Output is correct
7 Correct 19 ms 3416 KB Output is correct
8 Correct 42 ms 3664 KB Output is correct
9 Correct 32 ms 3668 KB Output is correct
10 Correct 55 ms 3664 KB Output is correct
11 Correct 40 ms 3924 KB Output is correct
12 Correct 26 ms 3920 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2908 KB Output is correct
2 Correct 228 ms 24636 KB Output is correct
3 Correct 227 ms 24516 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2908 KB Output is correct
2 Correct 228 ms 24636 KB Output is correct
3 Correct 227 ms 24516 KB Output is correct
4 Correct 17 ms 2652 KB Output is correct
5 Correct 186 ms 24516 KB Output is correct
6 Correct 165 ms 23240 KB Output is correct
7 Correct 154 ms 22980 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2844 KB Output is correct
2 Correct 459 ms 30440 KB Output is correct
3 Correct 473 ms 30544 KB Output is correct
4 Correct 476 ms 35920 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2844 KB Output is correct
2 Correct 459 ms 30440 KB Output is correct
3 Correct 473 ms 30544 KB Output is correct
4 Correct 476 ms 35920 KB Output is correct
5 Correct 19 ms 3420 KB Output is correct
6 Correct 454 ms 30992 KB Output is correct
7 Correct 460 ms 35748 KB Output is correct
8 Correct 399 ms 30036 KB Output is correct
9 Correct 389 ms 30156 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2904 KB Output is correct
2 Correct 451 ms 31256 KB Output is correct
3 Correct 481 ms 24052 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2904 KB Output is correct
2 Correct 451 ms 31256 KB Output is correct
3 Correct 481 ms 24052 KB Output is correct
4 Correct 20 ms 3420 KB Output is correct
5 Correct 439 ms 31812 KB Output is correct
6 Correct 435 ms 24532 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2904 KB Output is correct
2 Correct 461 ms 30400 KB Output is correct
3 Correct 447 ms 30408 KB Output is correct
4 Correct 482 ms 35724 KB Output is correct
5 Correct 20 ms 3672 KB Output is correct
6 Correct 452 ms 31224 KB Output is correct
7 Correct 476 ms 24048 KB Output is correct
8 Correct 515 ms 25180 KB Output is correct
9 Correct 515 ms 23584 KB Output is correct
10 Correct 715 ms 27016 KB Output is correct
11 Correct 748 ms 25880 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2904 KB Output is correct
2 Correct 461 ms 30400 KB Output is correct
3 Correct 447 ms 30408 KB Output is correct
4 Correct 482 ms 35724 KB Output is correct
5 Correct 20 ms 3672 KB Output is correct
6 Correct 452 ms 31224 KB Output is correct
7 Correct 476 ms 24048 KB Output is correct
8 Correct 515 ms 25180 KB Output is correct
9 Correct 515 ms 23584 KB Output is correct
10 Correct 715 ms 27016 KB Output is correct
11 Correct 748 ms 25880 KB Output is correct
12 Correct 19 ms 3408 KB Output is correct
13 Correct 443 ms 30800 KB Output is correct
14 Correct 454 ms 35668 KB Output is correct
15 Correct 367 ms 30036 KB Output is correct
16 Correct 389 ms 30020 KB Output is correct
17 Correct 19 ms 3420 KB Output is correct
18 Correct 454 ms 31684 KB Output is correct
19 Correct 453 ms 24492 KB Output is correct
20 Correct 497 ms 27224 KB Output is correct
21 Correct 481 ms 26852 KB Output is correct
22 Correct 592 ms 26296 KB Output is correct
23 Correct 803 ms 32660 KB Output is correct
24 Correct 777 ms 29564 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2904 KB Output is correct
2 Correct 58 ms 4580 KB Output is correct
3 Correct 36 ms 4184 KB Output is correct
4 Correct 74 ms 4448 KB Output is correct
5 Correct 49 ms 4540 KB Output is correct
6 Correct 28 ms 4436 KB Output is correct
7 Correct 18 ms 3676 KB Output is correct
8 Correct 190 ms 26392 KB Output is correct
9 Correct 227 ms 26524 KB Output is correct
10 Correct 20 ms 3668 KB Output is correct
11 Correct 479 ms 30392 KB Output is correct
12 Correct 458 ms 30544 KB Output is correct
13 Correct 472 ms 35812 KB Output is correct
14 Correct 19 ms 3676 KB Output is correct
15 Correct 441 ms 31312 KB Output is correct
16 Correct 463 ms 24148 KB Output is correct
17 Correct 501 ms 25256 KB Output is correct
18 Correct 490 ms 23636 KB Output is correct
19 Correct 731 ms 27016 KB Output is correct
20 Correct 760 ms 25780 KB Output is correct
21 Correct 245 ms 28480 KB Output is correct
22 Correct 236 ms 25816 KB Output is correct
23 Correct 406 ms 23840 KB Output is correct
24 Correct 403 ms 23892 KB Output is correct
25 Correct 513 ms 29644 KB Output is correct
26 Correct 410 ms 22328 KB Output is correct
27 Correct 340 ms 22732 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2904 KB Output is correct
2 Correct 58 ms 4580 KB Output is correct
3 Correct 36 ms 4184 KB Output is correct
4 Correct 74 ms 4448 KB Output is correct
5 Correct 49 ms 4540 KB Output is correct
6 Correct 28 ms 4436 KB Output is correct
7 Correct 18 ms 3676 KB Output is correct
8 Correct 190 ms 26392 KB Output is correct
9 Correct 227 ms 26524 KB Output is correct
10 Correct 20 ms 3668 KB Output is correct
11 Correct 479 ms 30392 KB Output is correct
12 Correct 458 ms 30544 KB Output is correct
13 Correct 472 ms 35812 KB Output is correct
14 Correct 19 ms 3676 KB Output is correct
15 Correct 441 ms 31312 KB Output is correct
16 Correct 463 ms 24148 KB Output is correct
17 Correct 501 ms 25256 KB Output is correct
18 Correct 490 ms 23636 KB Output is correct
19 Correct 731 ms 27016 KB Output is correct
20 Correct 760 ms 25780 KB Output is correct
21 Correct 245 ms 28480 KB Output is correct
22 Correct 236 ms 25816 KB Output is correct
23 Correct 406 ms 23840 KB Output is correct
24 Correct 403 ms 23892 KB Output is correct
25 Correct 513 ms 29644 KB Output is correct
26 Correct 410 ms 22328 KB Output is correct
27 Correct 340 ms 22732 KB Output is correct
28 Correct 18 ms 3420 KB Output is correct
29 Correct 42 ms 3664 KB Output is correct
30 Correct 32 ms 3668 KB Output is correct
31 Correct 53 ms 3664 KB Output is correct
32 Correct 40 ms 3924 KB Output is correct
33 Correct 25 ms 3920 KB Output is correct
34 Correct 17 ms 3416 KB Output is correct
35 Correct 177 ms 25876 KB Output is correct
36 Correct 165 ms 24080 KB Output is correct
37 Correct 162 ms 24260 KB Output is correct
38 Correct 19 ms 3420 KB Output is correct
39 Correct 427 ms 31120 KB Output is correct
40 Correct 441 ms 35628 KB Output is correct
41 Correct 399 ms 30040 KB Output is correct
42 Correct 372 ms 30036 KB Output is correct
43 Correct 19 ms 3412 KB Output is correct
44 Correct 427 ms 31824 KB Output is correct
45 Correct 442 ms 24444 KB Output is correct
46 Correct 463 ms 26960 KB Output is correct
47 Correct 489 ms 27012 KB Output is correct
48 Correct 640 ms 26452 KB Output is correct
49 Correct 789 ms 32652 KB Output is correct
50 Correct 797 ms 29524 KB Output is correct
51 Correct 200 ms 27636 KB Output is correct
52 Correct 176 ms 24660 KB Output is correct
53 Correct 161 ms 24912 KB Output is correct
54 Correct 136 ms 25028 KB Output is correct
55 Correct 141 ms 24772 KB Output is correct
56 Correct 367 ms 23376 KB Output is correct
57 Correct 351 ms 26828 KB Output is correct
58 Correct 436 ms 23656 KB Output is correct
59 Correct 344 ms 22096 KB Output is correct