oj.uz

답안 #556737

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
556737 2022-05-03T20:29:55 Z MilosMilutinovic Inside information (BOI21_servers) C++14
0 / 100
 402 ms 524288 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];
    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] = i;
    } else {
      go[i][0] = 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;
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:6:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    6 |   freopen("in.txt", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
servers.cpp:7:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |   freopen("out.txt", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Runtime error 375 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Runtime error 375 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Runtime error 383 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Runtime error 383 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 398 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 398 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 394 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 394 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Runtime error 387 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Runtime error 387 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Runtime error 402 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Runtime error 402 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -