Submission #389167

#	Time	Username	Problem	Language	Result	Execution time	Memory
389167		Hegdahl	Joker (BOI20_joker)	C++17	71 / 100	2011 ms	18656 KiB

Joker

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ar array

using namespace std;

const int mxN = 2e5;
const int mxM = 2e5;

const int mxR = ceil(sqrt(mxM));

ar<int, 2> edges[mxM];

int boss[mxN], under[mxN], toggle[mxN];

int tmp_boss[mxN], tmp_under[mxN], tmp_toggle[mxN];

vector<int> tmp_changes;

ar<int, 2> find(int i, bool tmp) {
  if (tmp_boss[i]!=-1 || i != boss[i]) {
    int b, bp;

    if (tmp_boss[i] != -1) {
      auto p = find(tmp_boss[i], tmp);
      b = p[0], bp = p[1];
    } else {
      auto p = find(boss[i], tmp);
      b = p[0], bp = p[1];
    }

    if (tmp) {
      tmp_boss[i] = b;

      int was_toggle = tmp_toggle[i];
      if (was_toggle == -1) was_toggle = toggle[i];
      tmp_toggle[i] = was_toggle ^ bp;

      tmp_changes.push_back(i);
    } else {
      boss[i] = b;
      toggle[i] ^= bp;
    }
  }

  int rb = tmp_boss[i], rp = tmp_toggle[i];
  if (rb == -1) rb = boss[i];
  if (rp == -1) rp = toggle[i];

  //if (tmp) cerr << "() ";
  //cerr << "find " << i << ' ' << rb << ' ' << rp << '\n';
  return {rb, rp};
}

bool unite(int _i, int _j, bool tmp) {
  // returns true as long as bipartite

  //cerr << '\n';
  //if (tmp) cerr << "() ";
  //cerr << _i << ' ' << _j << ' ' << tmp << '\n';

  auto [i, hi] = find(_i, tmp);
  auto [j, hj] = find(_j, tmp);

  //cerr << i << ' ' << j << ' ' << '\n';

  if (i == j) {
    return hi != hj;
  }

  //cerr << "h: " << hi << ' ' << hj << '\n';

  int under_i = tmp_under[i], under_j = tmp_under[j];
  if (under_i == -1) under_i = under[i];
  if (under_j == -1) under_j = under[j];

  if (under_i > under_j) swap(i, j);

  if (tmp) {
    tmp_boss[i] = j;
    tmp_under[j] = under_j + under_i;
    tmp_toggle[i] = toggle[i] ^ hi ^ hj ^ 1;

    tmp_changes.push_back(i);
    tmp_changes.push_back(j);
  } else {
    boss[i] = j;
    under[j] = under_j + under_i;

    toggle[i] ^= hi ^ hj ^ 1;
  }

  //cerr << "new boss: " << j << ' ' << toggle[j] << '\n';
  //cerr << "toggle: " << toggle[_i] << ' ' << toggle[_j] << '\n';

  return true;
}

int main() {
  ios::sync_with_stdio(0);cin.tie(0);

  int n, m, q;
  cin >> n >> m >> q;

  fill(tmp_boss, tmp_boss+n, -1);
  fill(tmp_under, tmp_under+n, -1);
  fill(tmp_toggle, tmp_toggle+n, -1);

  for (int mm = 0; mm < m; ++mm)
    for (int i : {0, 1})
      cin >> edges[mm][i], --edges[mm][i];

  iota(boss, boss+n, 0);
  fill(under, under+n, 1);
  fill(toggle, toggle+n, 0);

  bool all_bipartite = true;
  for (int mm = 0; all_bipartite && mm < m; ++mm)
    all_bipartite &= unite(edges[mm][0], edges[mm][1], false);

  if (all_bipartite) {
    for (int qq = 0; qq < q; ++qq)
      cout << "NO\n";
    return 0;
  }

  vector<int> buckets[mxM];


  int mxL = 0;
  vector<ar<int,2>> qs(q);
  for (int qq = 0; qq < q; ++qq) {
    for (int i : {0, 1})
      cin >> qs[qq][i], --qs[qq][i];
    mxL = max(mxL, qs[qq][0]);
  }

  int root = (int)ceil(sqrt((double)n*n/q));
  //cerr << "root " << root << '\n';

  for (int qq = 0; qq < q; ++qq)
    buckets[qs[qq][0]/root].push_back(qq);

  vector<bool> ans(q);

  for (int b = 0; b <= (m-1)/root; ++b) {
    if (buckets[b].empty()) continue;
    sort(buckets[b].begin(), buckets[b].end(), [&](int i, int j){
        return qs[i][1] > qs[j][1];
        });

    //cerr << "RESET\n";

    iota(boss, boss+n, 0);
    fill(under, under+n, 1);
    fill(toggle, toggle+n, 0);

    bool bipartite = true;

    for (int mm = 0; bipartite && mm < m; ++mm) {
      if (mm/root >= b) break;
      bipartite &= unite(edges[mm][0], edges[mm][1], false);
    }

    int R = m-1;

    for (int qq : buckets[b]) {
      //cerr << "qry: " << qs[qq][0] << ' ' << qs[qq][1] << '\n';

      while (bipartite && R > qs[qq][1]) {
        bipartite &= unite(edges[R][0], edges[R][1], false);
        --R;
      }

      bool tmp_bipartite = bipartite;
      int L = b*root;
      while (tmp_bipartite && L < qs[qq][0]) {
        tmp_bipartite &= unite(edges[L][0], edges[L][1], true);
        ++L;
      }

      ans[qq] = tmp_bipartite;

      //cerr << tmp_bipartite << '\n';

      //cerr << "tmp_reset\n";
      while (tmp_changes.size()) {
        int i = tmp_changes.back();
        tmp_changes.pop_back();
        tmp_boss[i] = -1;
        tmp_under[i] = -1;
        tmp_toggle[i] = -1;
      }
    }
  }

  for (bool a : ans)
    cout << (a?"NO\n":"YES\n");

}

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