oj.uz

답안 #556757

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
556757 2022-05-03T21:45:22 Z MilosMilutinovic Inside information (BOI21_servers) C++14
2.5 / 100
 3500 ms 44396 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];
    }
  }
  for (int i = 0; i < q; i++) {
    if (foo[i] != 'Q') {
      continue;
    }
    if (x[i] == y[i]) {
      cout << "yes" << '\n';
      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) {
      cout << "yes" << '\n';
    } else {
      cout << "no" << '\n';
    }
  }
  vector<int> ans(n, 1);
  vector<pair<int, int>> edges;
  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') {
      cout << ans[x[i]] << '\n';
    }
  }
  return 0;
}

Subtask #1
2.5 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 2040 KB Output is correct
2 Correct 247 ms 3188 KB Output is correct
3 Correct 226 ms 3408 KB Output is correct
4 Correct 245 ms 3532 KB Output is correct
5 Correct 213 ms 3608 KB Output is correct
6 Correct 217 ms 3380 KB Output is correct

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 2040 KB Output is correct
2 Correct 247 ms 3188 KB Output is correct
3 Correct 226 ms 3408 KB Output is correct
4 Correct 245 ms 3532 KB Output is correct
5 Correct 213 ms 3608 KB Output is correct
6 Correct 217 ms 3380 KB Output is correct
7 Incorrect 54 ms 2144 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 2136 KB Output is correct
2 Execution timed out 3574 ms 35988 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 2136 KB Output is correct
2 Execution timed out 3574 ms 35988 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 2048 KB Output is correct
2 Execution timed out 3570 ms 44396 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 2048 KB Output is correct
2 Execution timed out 3570 ms 44396 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 2124 KB Output is correct
2 Execution timed out 3575 ms 35788 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 2124 KB Output is correct
2 Execution timed out 3575 ms 35788 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 2044 KB Output is correct
2 Execution timed out 3585 ms 44260 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 2044 KB Output is correct
2 Execution timed out 3585 ms 44260 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 2068 KB Output is correct
2 Correct 249 ms 3352 KB Output is correct
3 Correct 233 ms 3284 KB Output is correct
4 Correct 241 ms 3304 KB Output is correct
5 Correct 206 ms 3516 KB Output is correct
6 Correct 218 ms 3356 KB Output is correct
7 Correct 51 ms 2124 KB Output is correct
8 Execution timed out 3573 ms 35944 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 51 ms 2068 KB Output is correct
2 Correct 249 ms 3352 KB Output is correct
3 Correct 233 ms 3284 KB Output is correct
4 Correct 241 ms 3304 KB Output is correct
5 Correct 206 ms 3516 KB Output is correct
6 Correct 218 ms 3356 KB Output is correct
7 Correct 51 ms 2124 KB Output is correct
8 Execution timed out 3573 ms 35944 KB Time limit exceeded
9 Halted 0 ms 0 KB -