oj.uz

Submission #484603

# Submission time Handle Problem Language Result Execution time Memory
484603 2021-11-04T16:20:31 Z BERNARB01 Joker (BOI20_joker) C++17
0 / 100
 978 ms 54260 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (int) 2e5 + 9;

int n, m, q, vis[N], bad[N], travt[N], l0g2[2 * N], id, d[N];
bool forall[202], ans[202][N];
vector<int> g[N];
pair<int, int> ed[N], rmq[18][2 * N];

void dfs0(int v, int dph) {
  d[v] = dph;
  rmq[0][id] = {dph, v};
  travt[v] = id++;
  for (int u : g[v]) {
    dfs0(u, dph + 1);
    rmq[0][id++] = {dph, v};
  }
}

inline int lca(int u, int v) {
  u = travt[u]; v = travt[v];
  if (u > v) {
    swap(u, v);
  }
  int l = l0g2[v - u + 1];
  return min(rmq[l][u], rmq[l][v - (1 << l) + 1]).second;
}
 
inline int dist(int u, int v) {
  int c = lca(u, v);
  return d[u] + d[v] - 2 * d[c];
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  for (int i = 2; i < 2 * N; i++) {
    l0g2[i] = 1 + l0g2[i / 2];
  }
  cin >> n >> m >> q;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    --u; --v;
    ed[i] = {u, v};
  }
  for (int l = 0; l < min(m, 201); l++) {
    memset(vis, 0, sizeof vis);
    memset(bad, 0, sizeof bad);
    for (int i = 0; i < n; i++) {
      g[i].clear();
    }
    for (int i = 0; i < m; i++) {
      auto& [u, v] = ed[i];
      if (u > v) {
        swap(u, v);
      }
    }
    for (int i = 0; i < l; i++) {
      auto& [u, v] = ed[i];
      if (vis[v]) {
        swap(u, v);
      }
      if (vis[v]) {
        bad[i] = 1;
      } else {
        g[u].push_back(v);
      }
      vis[u] = 1;
      vis[v] = 1;
    }
    for (int i = m - 1; i > l; i--) {
      auto& [u, v] = ed[i];
      if (vis[v]) {
        swap(u, v);
      }
      if (vis[v]) {
        bad[i] = 1;
      } else {
        g[u].push_back(v);
      }
      vis[u] = 1;
      vis[v] = 1;
    }
    int rt = (l == 0 ? ed[m - 1].first : ed[0].first);
    id = 0;
    dfs0(rt, 0);
    for (int j = 1; j < 18; j++) {
      for (int i = 0; i + (1 << j) <= id; i++) {
        rmq[j][i] = min(rmq[j - 1][i], rmq[j - 1][i + (1 << (j - 1))]);
      }
    }
    for (int i = 0; i < l; i++) {
      if (bad[i]) {
        auto [u, v] = ed[i];
        if (dist(u, v) % 2 == 0) {
          forall[l] = true;
          break;
        }
      }
    }
    for (int i = m - 1; i > l; i--) {
      if (bad[i]) {
        auto [u, v] = ed[i];
        ans[l][i] = ((dist(u, v) % 2 == 0) || forall[l]);
      }
    }
  }
  while (q--) {
    int l, r;
    cin >> l >> r;
    --l;
    cout << (ans[l][r] ? "YES" : "NO") << '\n';
  }
  return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8136 KB Output is correct
2 Correct 4 ms 8128 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Incorrect 5 ms 8128 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8136 KB Output is correct
2 Correct 4 ms 8128 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Incorrect 5 ms 8128 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8136 KB Output is correct
2 Correct 4 ms 8128 KB Output is correct
3 Incorrect 978 ms 54260 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8136 KB Output is correct
2 Correct 4 ms 8128 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Incorrect 5 ms 8128 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8136 KB Output is correct
2 Correct 4 ms 8128 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Incorrect 5 ms 8128 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8136 KB Output is correct
2 Correct 4 ms 8128 KB Output is correct
3 Correct 5 ms 8140 KB Output is correct
4 Incorrect 5 ms 8128 KB Output isn't correct
5 Halted 0 ms 0 KB -