oj.uz

Submission #556760

# Submission time Handle Problem Language Result Execution time Memory
556760 2022-05-03T21:50:08 Z MilosMilutinovic Inside information (BOI21_servers) C++14
50 / 100
 317 ms 43592 KB 
#include <bits/stdc++.h>

using namespace std;

class dsu {
  public:
  vector<int> p;
  vector<int> sz;
  int n;

  dsu(int _n) : n(_n) {
    p.resize(n);
    sz.resize(n);
    iota(p.begin(), p.end(), 0);
    fill(sz.begin(), sz.end(), 1);
  }

  inline int get(int x) {
    return (x == p[x] ? x : (p[x] = get(p[x])));
  }

  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      if (sz[x] > sz[y]) {
        swap(x, y);
      }
      p[x] = y;
      sz[y] += sz[x];
      return true;
    }
    return false;
  }
};

int main() {
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<vector<pair<int, int>>> g(n);
  int q = n - 1 + k;
  vector<char> foo(q);
  vector<int> x(q);
  vector<int> y(q);
  for (int i = 0; i < q; i++) {
    cin >> foo[i] >> x[i];
    if (foo[i] != 'C') {
      cin >> y[i];
    }
    --x[i], --y[i];
    if (foo[i] == 'S') {
      g[x[i]].emplace_back(y[i], i);
      g[y[i]].emplace_back(x[i], i);
    }
  }
  vector<int> par(n);
  vector<int> wei(n);
  vector<int> dep(n);
  function<void(int, int)> Dfs = [&](int u, int pr) {
    dep[u] = dep[pr] + 1;
    for (auto& e : g[u]) {
      int v = e.first;
      int w = e.second;
      if (v == pr) {
        continue;
      }
      par[v] = u;
      wei[v] = w;
      Dfs(v, u);
    }
  };
  Dfs(0, 0);
  wei[0] = 1000000;
  const int L = 20;
  vector<vector<int>> up(n, vector<int>(L));
  for (int i = 0; i < n; i++) {
    up[i][0] = par[i];
  }
  for (int j = 1; j < L; j++) {
    for (int i = 0; i < n; i++) {
      up[i][j] = up[up[i][j - 1]][j - 1];
    }
  }
  auto Lca = [&](int u, int v) {
    if (dep[u] < dep[v]) {
      swap(u, v);
    }
    for (int i = L - 1; i >= 0; i--) {
      if (dep[up[u][i]] >= dep[v]) {
        u = up[u][i];
      }
    }
    if (u == v) {
      return u;
    }
    for (int i = L - 1; i >= 0; i--) {
      if (up[u][i] != up[v][i]) {
        u = up[u][i];
        v = up[v][i];
      }
    }
    return up[u][0];
  };
  auto Lift = [&](int x, int d) {
    for (int i = L - 1; i >= 0; i--) {
      if (d >> i & 1) {
        x = up[x][i];
      }
    }
    return x;
  };
  vector<vector<int>> go(n, vector<int>(2, 0));
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    return dep[i] < dep[j];
  });
  for (int id = 1; id < n; id++) {
    int i = order[id];
    if (wei[par[i]] > wei[i]) {
      go[i][0] = go[par[i]][0];
      go[i][1] = par[i];
    } else {
      go[i][0] = par[i];
      go[i][1] = go[par[i]][1];
    }
  }
  vector<int> qans(q);
  for (int i = 0; i < q; i++) {
    if (foo[i] != 'Q') {
      continue;
    }
    if (x[i] == y[i]) {
      qans[i] = 1;
      continue;
    }
    int z = Lca(x[i], y[i]);
    bool ok = true;
    if (x[i] != z && y[i] != z) {
      int p_x = Lift(x[i], dep[x[i]] - dep[z] - 1);
      int p_y = Lift(y[i], dep[y[i]] - dep[z] - 1);
      if (wei[p_y] > wei[p_x]) {
        ok = false;
      }
    }
    if (x[i] != z && wei[x[i]] > i) {
      ok = false;
    }
    if (y[i] != z && wei[Lift(y[i], dep[y[i]] - dep[z] - 1)] > i) {
      ok = false;
    }
    if (dep[go[y[i]][0]] <= dep[z] && dep[go[x[i]][1]] <= dep[z] && ok) {
      qans[i] = 1;
    } else {
      qans[i] = 0;
    }
  }
  vector<int> ans(n, 1);
  vector<pair<int, int>> edges;
  if (n <= 4000) {
    for (int i = 0; i < q; i++) {
      if (foo[i] == 'S') {
        edges.emplace_back(x[i], y[i]);
        dsu d(n);
        vector<int> nans(n, 1);
        for (int j = edges.size() - 1; j >= 0; j--) {
          int u = edges[j].first;
          int v = edges[j].second;
          nans[u] += d.sz[d.get(v)];
          nans[v] += d.sz[d.get(u)];
          d.unite(u, v);
        }
        swap(ans, nans);
      }
      if (foo[i] == 'C') {
        qans[i] = ans[x[i]];
      }
    }
  }
  for (int i = 0; i < q; i++) {
    if (foo[i] == 'Q') {
      cout << (qans[i] == 0 ? "no" : "yes") << '\n';
    } else if (foo[i] == 'C') {
      cout << qans[i] <<  '\n';
    }
  }
  return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 2724 KB Output is correct
2 Correct 233 ms 3988 KB Output is correct
3 Correct 228 ms 4136 KB Output is correct
4 Correct 242 ms 4076 KB Output is correct
5 Correct 205 ms 4268 KB Output is correct
6 Correct 221 ms 4096 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 2724 KB Output is correct
2 Correct 233 ms 3988 KB Output is correct
3 Correct 228 ms 4136 KB Output is correct
4 Correct 242 ms 4076 KB Output is correct
5 Correct 205 ms 4268 KB Output is correct
6 Correct 221 ms 4096 KB Output is correct
7 Incorrect 51 ms 2684 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2828 KB Output is correct
2 Correct 181 ms 34956 KB Output is correct
3 Correct 172 ms 35116 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2828 KB Output is correct
2 Correct 181 ms 34956 KB Output is correct
3 Correct 172 ms 35116 KB Output is correct
4 Correct 48 ms 2900 KB Output is correct
5 Incorrect 167 ms 37132 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2764 KB Output is correct
2 Correct 161 ms 43340 KB Output is correct
3 Correct 170 ms 43508 KB Output is correct
4 Correct 206 ms 43568 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2764 KB Output is correct
2 Correct 161 ms 43340 KB Output is correct
3 Correct 170 ms 43508 KB Output is correct
4 Correct 206 ms 43568 KB Output is correct
5 Incorrect 37 ms 2888 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2748 KB Output is correct
2 Correct 184 ms 34860 KB Output is correct
3 Correct 162 ms 35216 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2748 KB Output is correct
2 Correct 184 ms 34860 KB Output is correct
3 Correct 162 ms 35216 KB Output is correct
4 Incorrect 49 ms 2916 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2764 KB Output is correct
2 Correct 170 ms 43544 KB Output is correct
3 Correct 183 ms 43560 KB Output is correct
4 Correct 200 ms 43568 KB Output is correct
5 Correct 48 ms 3116 KB Output is correct
6 Correct 182 ms 35064 KB Output is correct
7 Correct 165 ms 35100 KB Output is correct
8 Correct 248 ms 35860 KB Output is correct
9 Correct 201 ms 35944 KB Output is correct
10 Correct 217 ms 38592 KB Output is correct
11 Correct 317 ms 37964 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2764 KB Output is correct
2 Correct 170 ms 43544 KB Output is correct
3 Correct 183 ms 43560 KB Output is correct
4 Correct 200 ms 43568 KB Output is correct
5 Correct 48 ms 3116 KB Output is correct
6 Correct 182 ms 35064 KB Output is correct
7 Correct 165 ms 35100 KB Output is correct
8 Correct 248 ms 35860 KB Output is correct
9 Correct 201 ms 35944 KB Output is correct
10 Correct 217 ms 38592 KB Output is correct
11 Correct 317 ms 37964 KB Output is correct
12 Incorrect 38 ms 2888 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2828 KB Output is correct
2 Correct 240 ms 3996 KB Output is correct
3 Correct 228 ms 4104 KB Output is correct
4 Correct 234 ms 4192 KB Output is correct
5 Correct 204 ms 4348 KB Output is correct
6 Correct 221 ms 4184 KB Output is correct
7 Correct 49 ms 2824 KB Output is correct
8 Correct 181 ms 34940 KB Output is correct
9 Correct 183 ms 35008 KB Output is correct
10 Correct 40 ms 2984 KB Output is correct
11 Correct 162 ms 43568 KB Output is correct
12 Correct 161 ms 43592 KB Output is correct
13 Correct 198 ms 43564 KB Output is correct
14 Correct 51 ms 2952 KB Output is correct
15 Correct 182 ms 35092 KB Output is correct
16 Correct 169 ms 35124 KB Output is correct
17 Correct 236 ms 35812 KB Output is correct
18 Correct 195 ms 35900 KB Output is correct
19 Correct 221 ms 38616 KB Output is correct
20 Correct 315 ms 37932 KB Output is correct
21 Correct 188 ms 35028 KB Output is correct
22 Correct 182 ms 35112 KB Output is correct
23 Correct 185 ms 35600 KB Output is correct
24 Correct 201 ms 35628 KB Output is correct
25 Correct 203 ms 37316 KB Output is correct
26 Correct 157 ms 34872 KB Output is correct
27 Correct 147 ms 34928 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 50 ms 2828 KB Output is correct
2 Correct 240 ms 3996 KB Output is correct
3 Correct 228 ms 4104 KB Output is correct
4 Correct 234 ms 4192 KB Output is correct
5 Correct 204 ms 4348 KB Output is correct
6 Correct 221 ms 4184 KB Output is correct
7 Correct 49 ms 2824 KB Output is correct
8 Correct 181 ms 34940 KB Output is correct
9 Correct 183 ms 35008 KB Output is correct
10 Correct 40 ms 2984 KB Output is correct
11 Correct 162 ms 43568 KB Output is correct
12 Correct 161 ms 43592 KB Output is correct
13 Correct 198 ms 43564 KB Output is correct
14 Correct 51 ms 2952 KB Output is correct
15 Correct 182 ms 35092 KB Output is correct
16 Correct 169 ms 35124 KB Output is correct
17 Correct 236 ms 35812 KB Output is correct
18 Correct 195 ms 35900 KB Output is correct
19 Correct 221 ms 38616 KB Output is correct
20 Correct 315 ms 37932 KB Output is correct
21 Correct 188 ms 35028 KB Output is correct
22 Correct 182 ms 35112 KB Output is correct
23 Correct 185 ms 35600 KB Output is correct
24 Correct 201 ms 35628 KB Output is correct
25 Correct 203 ms 37316 KB Output is correct
26 Correct 157 ms 34872 KB Output is correct
27 Correct 147 ms 34928 KB Output is correct
28 Incorrect 50 ms 2896 KB Extra information in the output file
29 Halted 0 ms 0 KB -