oj.uz

Submission #556740

# Submission time Handle Problem Language Result Execution time Memory
556740 2022-05-03T20:36:35 Z MilosMilutinovic Inside information (BOI21_servers) C++14
50 / 100
 367 ms 41784 KB 
#include <bits/stdc++.h>

using namespace std;

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] >> y[i];
    --x[i], --y[i];
    assert(x[i] >= 0 && x[i] < n && y[i] >= 0 && y[i] < n);
    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';
    }
  }
  return 0;
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1740 KB Output is correct
2 Correct 69 ms 3064 KB Output is correct
3 Correct 67 ms 3120 KB Output is correct
4 Correct 83 ms 3148 KB Output is correct
5 Correct 60 ms 3388 KB Output is correct
6 Correct 65 ms 3172 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 49 ms 1740 KB Output is correct
2 Correct 69 ms 3064 KB Output is correct
3 Correct 67 ms 3120 KB Output is correct
4 Correct 83 ms 3148 KB Output is correct
5 Correct 60 ms 3388 KB Output is correct
6 Correct 65 ms 3172 KB Output is correct
7 Runtime error 3 ms 2644 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 1728 KB Output is correct
2 Correct 212 ms 33240 KB Output is correct
3 Correct 201 ms 33176 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 62 ms 1728 KB Output is correct
2 Correct 212 ms 33240 KB Output is correct
3 Correct 201 ms 33176 KB Output is correct
4 Runtime error 3 ms 2636 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1644 KB Output is correct
2 Correct 194 ms 41744 KB Output is correct
3 Correct 187 ms 41684 KB Output is correct
4 Correct 253 ms 41752 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1644 KB Output is correct
2 Correct 194 ms 41744 KB Output is correct
3 Correct 187 ms 41684 KB Output is correct
4 Correct 253 ms 41752 KB Output is correct
5 Runtime error 3 ms 2644 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 1648 KB Output is correct
2 Correct 200 ms 33308 KB Output is correct
3 Correct 207 ms 33320 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 1648 KB Output is correct
2 Correct 200 ms 33308 KB Output is correct
3 Correct 207 ms 33320 KB Output is correct
4 Runtime error 3 ms 2560 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1712 KB Output is correct
2 Correct 176 ms 41764 KB Output is correct
3 Correct 178 ms 41784 KB Output is correct
4 Correct 261 ms 41616 KB Output is correct
5 Correct 52 ms 2000 KB Output is correct
6 Correct 191 ms 33156 KB Output is correct
7 Correct 202 ms 33356 KB Output is correct
8 Correct 295 ms 33952 KB Output is correct
9 Correct 207 ms 34000 KB Output is correct
10 Correct 303 ms 36748 KB Output is correct
11 Correct 346 ms 36060 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1712 KB Output is correct
2 Correct 176 ms 41764 KB Output is correct
3 Correct 178 ms 41784 KB Output is correct
4 Correct 261 ms 41616 KB Output is correct
5 Correct 52 ms 2000 KB Output is correct
6 Correct 191 ms 33156 KB Output is correct
7 Correct 202 ms 33356 KB Output is correct
8 Correct 295 ms 33952 KB Output is correct
9 Correct 207 ms 34000 KB Output is correct
10 Correct 303 ms 36748 KB Output is correct
11 Correct 346 ms 36060 KB Output is correct
12 Runtime error 2 ms 2644 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 1740 KB Output is correct
2 Correct 82 ms 3016 KB Output is correct
3 Correct 67 ms 3160 KB Output is correct
4 Correct 78 ms 3176 KB Output is correct
5 Correct 64 ms 3404 KB Output is correct
6 Correct 64 ms 3128 KB Output is correct
7 Correct 57 ms 2080 KB Output is correct
8 Correct 213 ms 33220 KB Output is correct
9 Correct 214 ms 33344 KB Output is correct
10 Correct 46 ms 2036 KB Output is correct
11 Correct 202 ms 41676 KB Output is correct
12 Correct 174 ms 41704 KB Output is correct
13 Correct 241 ms 41732 KB Output is correct
14 Correct 54 ms 1992 KB Output is correct
15 Correct 196 ms 33248 KB Output is correct
16 Correct 205 ms 33312 KB Output is correct
17 Correct 294 ms 33928 KB Output is correct
18 Correct 226 ms 33996 KB Output is correct
19 Correct 245 ms 36772 KB Output is correct
20 Correct 367 ms 36024 KB Output is correct
21 Correct 246 ms 33304 KB Output is correct
22 Correct 199 ms 33248 KB Output is correct
23 Correct 217 ms 33664 KB Output is correct
24 Correct 252 ms 33652 KB Output is correct
25 Correct 223 ms 35448 KB Output is correct
26 Correct 186 ms 33088 KB Output is correct
27 Correct 148 ms 33028 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 56 ms 1740 KB Output is correct
2 Correct 82 ms 3016 KB Output is correct
3 Correct 67 ms 3160 KB Output is correct
4 Correct 78 ms 3176 KB Output is correct
5 Correct 64 ms 3404 KB Output is correct
6 Correct 64 ms 3128 KB Output is correct
7 Correct 57 ms 2080 KB Output is correct
8 Correct 213 ms 33220 KB Output is correct
9 Correct 214 ms 33344 KB Output is correct
10 Correct 46 ms 2036 KB Output is correct
11 Correct 202 ms 41676 KB Output is correct
12 Correct 174 ms 41704 KB Output is correct
13 Correct 241 ms 41732 KB Output is correct
14 Correct 54 ms 1992 KB Output is correct
15 Correct 196 ms 33248 KB Output is correct
16 Correct 205 ms 33312 KB Output is correct
17 Correct 294 ms 33928 KB Output is correct
18 Correct 226 ms 33996 KB Output is correct
19 Correct 245 ms 36772 KB Output is correct
20 Correct 367 ms 36024 KB Output is correct
21 Correct 246 ms 33304 KB Output is correct
22 Correct 199 ms 33248 KB Output is correct
23 Correct 217 ms 33664 KB Output is correct
24 Correct 252 ms 33652 KB Output is correct
25 Correct 223 ms 35448 KB Output is correct
26 Correct 186 ms 33088 KB Output is correct
27 Correct 148 ms 33028 KB Output is correct
28 Runtime error 3 ms 2644 KB Execution killed with signal 6
29 Halted 0 ms 0 KB -