oj.uz

Submission #914807

# Submission time Handle Problem Language Result Execution time Memory
914807 2024-01-22T17:23:14 Z nima_aryan Inside information (BOI21_servers) C++17
100 / 100
 569 ms 29104 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> label;

  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);

    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];
      }
    }
    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 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;
    });
    {
      int l = 0;
      auto labeling = [&](auto self, int x, int p) -> void {
        label[x] = l;
        for (auto [y, _] : adj[x]) {
          if (y != p && alive[y]) {
            self(self, y, x);
          }
        }
      };
      for (auto [u, _] : adj[c]) {
        if (alive[u]) {
          ++l;
          labeling(labeling, u, c);
        }
      }
    }

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

    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 (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 (label[a] == label[d]) {
              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 17 ms 2904 KB Output is correct
2 Correct 31 ms 3432 KB Output is correct
3 Correct 24 ms 3420 KB Output is correct
4 Correct 34 ms 3420 KB Output is correct
5 Correct 31 ms 3668 KB Output is correct
6 Correct 25 ms 3412 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2904 KB Output is correct
2 Correct 31 ms 3432 KB Output is correct
3 Correct 24 ms 3420 KB Output is correct
4 Correct 34 ms 3420 KB Output is correct
5 Correct 31 ms 3668 KB Output is correct
6 Correct 25 ms 3412 KB Output is correct
7 Correct 18 ms 2648 KB Output is correct
8 Correct 29 ms 2908 KB Output is correct
9 Correct 24 ms 2904 KB Output is correct
10 Correct 30 ms 2900 KB Output is correct
11 Correct 32 ms 3164 KB Output is correct
12 Correct 24 ms 3076 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2852 KB Output is correct
2 Correct 182 ms 25064 KB Output is correct
3 Correct 175 ms 25280 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2852 KB Output is correct
2 Correct 182 ms 25064 KB Output is correct
3 Correct 175 ms 25280 KB Output is correct
4 Correct 17 ms 2780 KB Output is correct
5 Correct 204 ms 24996 KB Output is correct
6 Correct 163 ms 23748 KB Output is correct
7 Correct 154 ms 23496 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2904 KB Output is correct
2 Correct 304 ms 23776 KB Output is correct
3 Correct 279 ms 23800 KB Output is correct
4 Correct 297 ms 29088 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2904 KB Output is correct
2 Correct 304 ms 23776 KB Output is correct
3 Correct 279 ms 23800 KB Output is correct
4 Correct 297 ms 29088 KB Output is correct
5 Correct 18 ms 2652 KB Output is correct
6 Correct 305 ms 24428 KB Output is correct
7 Correct 293 ms 28936 KB Output is correct
8 Correct 263 ms 23796 KB Output is correct
9 Correct 251 ms 23760 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2908 KB Output is correct
2 Correct 252 ms 26696 KB Output is correct
3 Correct 252 ms 19896 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2908 KB Output is correct
2 Correct 252 ms 26696 KB Output is correct
3 Correct 252 ms 19896 KB Output is correct
4 Correct 17 ms 2648 KB Output is correct
5 Correct 264 ms 27132 KB Output is correct
6 Correct 260 ms 20112 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 300 ms 23752 KB Output is correct
3 Correct 266 ms 23848 KB Output is correct
4 Correct 295 ms 29040 KB Output is correct
5 Correct 17 ms 2852 KB Output is correct
6 Correct 258 ms 26684 KB Output is correct
7 Correct 227 ms 19880 KB Output is correct
8 Correct 288 ms 20888 KB Output is correct
9 Correct 265 ms 20376 KB Output is correct
10 Correct 352 ms 24284 KB Output is correct
11 Correct 311 ms 23384 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 300 ms 23752 KB Output is correct
3 Correct 266 ms 23848 KB Output is correct
4 Correct 295 ms 29040 KB Output is correct
5 Correct 17 ms 2852 KB Output is correct
6 Correct 258 ms 26684 KB Output is correct
7 Correct 227 ms 19880 KB Output is correct
8 Correct 288 ms 20888 KB Output is correct
9 Correct 265 ms 20376 KB Output is correct
10 Correct 352 ms 24284 KB Output is correct
11 Correct 311 ms 23384 KB Output is correct
12 Correct 17 ms 2652 KB Output is correct
13 Correct 301 ms 24308 KB Output is correct
14 Correct 300 ms 28904 KB Output is correct
15 Correct 259 ms 23836 KB Output is correct
16 Correct 257 ms 23820 KB Output is correct
17 Correct 18 ms 2652 KB Output is correct
18 Correct 261 ms 27020 KB Output is correct
19 Correct 226 ms 20168 KB Output is correct
20 Correct 249 ms 21396 KB Output is correct
21 Correct 298 ms 21096 KB Output is correct
22 Correct 350 ms 24056 KB Output is correct
23 Correct 569 ms 25944 KB Output is correct
24 Correct 455 ms 25512 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 30 ms 3420 KB Output is correct
3 Correct 26 ms 3420 KB Output is correct
4 Correct 31 ms 3492 KB Output is correct
5 Correct 30 ms 3580 KB Output is correct
6 Correct 29 ms 3420 KB Output is correct
7 Correct 18 ms 2904 KB Output is correct
8 Correct 190 ms 25052 KB Output is correct
9 Correct 202 ms 25068 KB Output is correct
10 Correct 17 ms 2904 KB Output is correct
11 Correct 297 ms 23944 KB Output is correct
12 Correct 281 ms 23792 KB Output is correct
13 Correct 300 ms 29104 KB Output is correct
14 Correct 17 ms 2904 KB Output is correct
15 Correct 258 ms 26700 KB Output is correct
16 Correct 231 ms 20032 KB Output is correct
17 Correct 250 ms 20572 KB Output is correct
18 Correct 274 ms 20416 KB Output is correct
19 Correct 362 ms 24428 KB Output is correct
20 Correct 316 ms 23324 KB Output is correct
21 Correct 212 ms 27204 KB Output is correct
22 Correct 218 ms 24760 KB Output is correct
23 Correct 200 ms 20604 KB Output is correct
24 Correct 232 ms 20588 KB Output is correct
25 Correct 338 ms 25544 KB Output is correct
26 Correct 249 ms 18884 KB Output is correct
27 Correct 249 ms 18940 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 30 ms 3420 KB Output is correct
3 Correct 26 ms 3420 KB Output is correct
4 Correct 31 ms 3492 KB Output is correct
5 Correct 30 ms 3580 KB Output is correct
6 Correct 29 ms 3420 KB Output is correct
7 Correct 18 ms 2904 KB Output is correct
8 Correct 190 ms 25052 KB Output is correct
9 Correct 202 ms 25068 KB Output is correct
10 Correct 17 ms 2904 KB Output is correct
11 Correct 297 ms 23944 KB Output is correct
12 Correct 281 ms 23792 KB Output is correct
13 Correct 300 ms 29104 KB Output is correct
14 Correct 17 ms 2904 KB Output is correct
15 Correct 258 ms 26700 KB Output is correct
16 Correct 231 ms 20032 KB Output is correct
17 Correct 250 ms 20572 KB Output is correct
18 Correct 274 ms 20416 KB Output is correct
19 Correct 362 ms 24428 KB Output is correct
20 Correct 316 ms 23324 KB Output is correct
21 Correct 212 ms 27204 KB Output is correct
22 Correct 218 ms 24760 KB Output is correct
23 Correct 200 ms 20604 KB Output is correct
24 Correct 232 ms 20588 KB Output is correct
25 Correct 338 ms 25544 KB Output is correct
26 Correct 249 ms 18884 KB Output is correct
27 Correct 249 ms 18940 KB Output is correct
28 Correct 17 ms 2648 KB Output is correct
29 Correct 32 ms 2972 KB Output is correct
30 Correct 24 ms 2908 KB Output is correct
31 Correct 37 ms 3068 KB Output is correct
32 Correct 32 ms 3152 KB Output is correct
33 Correct 25 ms 3160 KB Output is correct
34 Correct 18 ms 2652 KB Output is correct
35 Correct 197 ms 25028 KB Output is correct
36 Correct 157 ms 23596 KB Output is correct
37 Correct 166 ms 23620 KB Output is correct
38 Correct 18 ms 2652 KB Output is correct
39 Correct 293 ms 24432 KB Output is correct
40 Correct 291 ms 28864 KB Output is correct
41 Correct 267 ms 23700 KB Output is correct
42 Correct 270 ms 23824 KB Output is correct
43 Correct 19 ms 2652 KB Output is correct
44 Correct 275 ms 27180 KB Output is correct
45 Correct 268 ms 20108 KB Output is correct
46 Correct 283 ms 21136 KB Output is correct
47 Correct 291 ms 21064 KB Output is correct
48 Correct 363 ms 23972 KB Output is correct
49 Correct 550 ms 26036 KB Output is correct
50 Correct 504 ms 25688 KB Output is correct
51 Correct 197 ms 26688 KB Output is correct
52 Correct 170 ms 23748 KB Output is correct
53 Correct 156 ms 23496 KB Output is correct
54 Correct 147 ms 23564 KB Output is correct
55 Correct 150 ms 23260 KB Output is correct
56 Correct 171 ms 19896 KB Output is correct
57 Correct 255 ms 23244 KB Output is correct
58 Correct 262 ms 19796 KB Output is correct
59 Correct 228 ms 18980 KB Output is correct