Submission #651979

#	Time	Username	Problem	Language	Result	Execution time	Memory
651979		lunchbox1	Joker (BOI20_joker)	C++17	100 / 100	219 ms	14228 KiB

Joker

/*
 author: lunchbox
 problem link: https://oj.uz/problem/view/BOI20_joker
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5, M = 2e5 + 5;

pair<int, int> p[N];
int s[N];

pair<int, int> find(int i) {
 if (p[i].first == i) return {i, 0};
 auto [x, u] = find(p[i].first);
 return {x, u ^ p[i].second};
}
vector<tuple<int, int, pair<int, int>>> un;
bool join(int i, int j) {
 auto [x, u] = find(i); auto [y, v] = find(j);
 if (x == y) {
  un.push_back({-1, -1, {-1, -1}});
  return u == v;
 }
 if (s[x] < s[y]) swap(x, y);
 un.push_back({x, y, p[y]});
 s[x] += s[y], p[y] = {x, 1 ^ u ^ v};
 return 0;
}
void undo() {
 auto [i, j, p_] = un.back();
 if (i != -1) s[i] -= s[j], p[j] = p_;
 un.pop_back();
}

int u[M], v[M], o[M];

void solve(int l, int r, int l_, int r_) {
 if (l > r) return;
 if (l_ == r_) {
  for (int i = l; i <= r; i++) o[i] = l_;
  return;
 }
 int m = (l + r) / 2;
 bool g = 0;
 for (int i = l; i <= m; i++) g |= join(u[i], v[i]);
 int t = r_ + 1;
 while (!g) t--, g |= join(u[t], v[t]);
 o[m] = t;
 for (int i = t; i <= r_; i++) undo();
 solve(m + 1, r, t, r_);
 for (int i = l; i <= m; i++) undo();
 for (int i = t + 1; i <= r_; i++) join(u[i], v[i]);
 solve(l, m - 1, l_, t);
 for (int i = t + 1; i <= r_; i++) undo();
}

int main() {
 ios::sync_with_stdio(false), cin.tie(NULL);
 int n, m, q; cin >> n >> m >> q;
 for (int i = 0; i < n; i++) s[i] = 1, p[i] = {i, 0};
 int g = m + 1;
 for (int i = 1; i <= m; i++) {
  cin >> u[i] >> v[i], u[i]--, v[i]--;
  if (join(u[i], v[i])) g = min(g, i);
 }
 if (g == m + 1) {
  while (q--)
   cout << "NO" << '\n';
  return 0;
 }
 for (int i = g; i <= m; i++) o[i] = m + 1;
 for (int i = 1; i <= m; i++) undo();
 int t = m;
 while (!join(u[t], v[t])) t--;
 o[0] = t;
 for (int i = t; i <= m; i++) undo();
 solve(1, g - 1, o[0], m);
 for (int i = 0; i < n; i++) s[i] = 1, p[i] = {i, 0};
 while (q--) {
  int l, r; cin >> l >> r;
  cout << (o[l - 1] > r ? "YES" : "NO") << '\n';
 }
}

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