oj.uz

Submission #389162

# Submission time Handle Problem Language Result Execution time Memory
389162 2021-04-13T18:36:03 Z Hegdahl Joker (BOI20_joker) C++17
0 / 100
 0 ms 332 KB 
#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 < n; ++qq)
      cout << "NO\n";
    return 0;
  }

  vector<int> buckets[mxM];

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

  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];
    buckets[qs[qq][0]/root].push_back(qq);
  }

  vector<bool> ans(q);

  for (int b = 0; b <= (m-1)/root; ++b) {
    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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -