Submission #484604

#	Time	Username	Problem	Language	Result	Execution time	Memory
484604		BERNARB01	Joker (BOI20_joker)	C++17	0 / 100	2089 ms	57844 KiB

Joker

#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 pr, int dph) {
  d[v] = dph;
  rmq[0][id] = {dph, v};
  travt[v] = id++;
  vis[v] = 1;
  for (int u : g[v]) {
    if (u == pr || vis[u]) {
      continue;
    }
    dfs0(u, v, 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];
}

struct dsu {
  vector<int> e;
  dsu(int _n) {
    e.assign(_n, -1);
  }
  inline int get(int u) {
    return (e[u] < 0 ? u : (e[u] = get(e[u])));
  }
  inline bool unite(int u, int v) {
    u = get(u); v = get(v);
    if (u == v) {
      return false;
    }
    if (e[u] < e[v]) {
      swap(u, v);
    }
    e[v] += e[u];
    e[u] = v;
    return true;
  }
};

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();
    }
    dsu se(n);
    for (int i = 0; i < l; i++) {
      auto& [u, v] = ed[i];
      if (se.unite(u, v)) {
        g[u].push_back(v);
        g[v].push_back(u);
      } else {
        bad[i] = 1;
      }
    }
    for (int i = m - 1; i > l; i--) {
      auto& [u, v] = ed[i];
      if (se.unite(u, v)) {
        g[u].push_back(v);
        g[v].push_back(u);
      } else {
        bad[i] = 1;
      }
    }
    id = 0;
    for (int i = 0; i < l; i++) {
      if (!vis[ed[i].first]) {
        dfs0(ed[i].first, -1, 0);
      }
    }
    for (int i = m - 1; i > l; i--) {
      if (!vis[ed[i].first]) {
        dfs0(ed[i].first, -1, 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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29