Submission #1093493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093493		duckindog	Joker (BOI20_joker)	C++17	100 / 100	305 ms	14516 KiB

Joker

#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10;
int n, m, q;
struct Edge { 
  int u, v;
  friend istream& operator >> (istream& is, auto& rhs) { 
    return is >> rhs.u >> rhs.v;
  }
} edge[N];

int id[N], cnt;
bool mk[N];
vector<tuple<int, int, int, int, int, int>> undo;
int root(int u) { return id[u] < 0 ? u : root(id[u]); }
bool chk(int u) { return id[u] < 0 ? mk[u] : mk[u] ^ chk(id[u]); }
void add(int u, int v) { 
  int oU = u, oV = v;
  u = root(u); v = root(v);
  if (u == v) { 
    undo.emplace_back(0, 0, 0, 0, 0, cnt);
    cnt += chk(oU) == chk(oV);
    return;
  }
  
  if (id[u] > id[v]) swap(u, v);
  undo.emplace_back(u, id[u], v, id[v], mk[v], cnt);

  mk[v] ^= (chk(oU) == chk(oV));
  id[u] += id[v];
  id[v] = u;
}
void rollBack() { 
  auto [u, idU, v, idV, mkV, pCnt] = undo.back(); undo.pop_back();
  id[u] = idU;
  id[v] = idV;
  mk[v] = mkV;
  cnt = pCnt;
}

int f[N];
void dnc(int l, int r, int lt, int rt) { 
  if (l > r) return;
  int mid = (l + r) >> 1;
  auto& ret = f[mid];

  for (int i = l; i < mid; ++i) add(edge[i].u, edge[i].v);
  for (int i = rt; i >= max(mid + 1, lt); --i) add(edge[i].u, edge[i].v);

  for (int i = max(mid + 1, lt); i <= rt; ++i) { 
    if (cnt) ret = i - 1;
    rollBack();
  } if (cnt) ret = rt;
  
  int nxtR = (!ret ? max(mid + 1, lt) : ret),
      nxtL = (!ret ? mid : ret);

  add(edge[mid].u, edge[mid].v);
  dnc(mid + 1, r, nxtR, rt);
  for (int i = mid; i >= l; --i) rollBack();

  for (int i = rt; i > nxtL; --i) add(edge[i].u, edge[i].v);
  dnc(l, mid - 1, lt, nxtL);
  for (int i = rt; i > nxtL; --i) rollBack();
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m >> q;
  for (int i = 1; i <= m; ++i) cin >> edge[i];

  memset(id, -1, sizeof id);
  dnc(1, m, 1, m);

  while (q--) { 
    int l, r; cin >> l >> r;
    cout << (r <= f[l] ? "YES" : "NO") << "\n";
  }
}

Compilation message (stderr)

Joker.cpp:9:45: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    9 |   friend istream& operator >> (istream& is, auto& rhs) {
      |                                             ^~~~

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 10 / 10
• Subtask 5: 22 / 22
• Subtask 6: 29 / 29