oj.uz

Submission #389160

# Submission time Handle Problem Language Result Execution time Memory
389160 2021-04-13T18:31:20 Z Hegdahl Joker (BOI20_joker) C++17
14 / 100
 2000 ms 16304 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];

  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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4944 KB Output is correct
7 Correct 3 ms 4944 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 5068 KB Output is correct
10 Correct 3 ms 5068 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 4940 KB Output is correct
16 Correct 3 ms 4996 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 3 ms 5068 KB Output is correct
19 Correct 3 ms 4944 KB Output is correct
20 Correct 3 ms 5068 KB Output is correct
21 Correct 3 ms 4940 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 3 ms 4940 KB Output is correct
24 Correct 4 ms 5068 KB Output is correct
25 Correct 3 ms 4940 KB Output is correct
26 Correct 3 ms 4944 KB Output is correct
27 Correct 3 ms 5004 KB Output is correct
28 Correct 3 ms 5068 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4944 KB Output is correct
7 Correct 3 ms 4944 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 5068 KB Output is correct
10 Correct 3 ms 5068 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 4940 KB Output is correct
16 Correct 3 ms 4996 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 3 ms 5068 KB Output is correct
19 Correct 3 ms 4944 KB Output is correct
20 Correct 3 ms 5068 KB Output is correct
21 Correct 3 ms 4940 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 3 ms 4940 KB Output is correct
24 Correct 4 ms 5068 KB Output is correct
25 Correct 3 ms 4940 KB Output is correct
26 Correct 3 ms 4944 KB Output is correct
27 Correct 3 ms 5004 KB Output is correct
28 Correct 3 ms 5068 KB Output is correct
29 Correct 7 ms 5068 KB Output is correct
30 Correct 6 ms 5172 KB Output is correct
31 Correct 6 ms 5068 KB Output is correct
32 Correct 5 ms 5068 KB Output is correct
33 Correct 5 ms 5068 KB Output is correct
34 Correct 6 ms 5068 KB Output is correct
35 Correct 7 ms 5068 KB Output is correct
36 Correct 6 ms 5068 KB Output is correct
37 Correct 10 ms 5284 KB Output is correct
38 Correct 10 ms 5152 KB Output is correct
39 Correct 7 ms 5196 KB Output is correct
40 Correct 6 ms 5068 KB Output is correct
41 Correct 6 ms 5068 KB Output is correct
42 Correct 7 ms 5068 KB Output is correct
43 Correct 5 ms 5068 KB Output is correct
44 Correct 5 ms 5068 KB Output is correct
45 Correct 5 ms 5068 KB Output is correct
46 Correct 6 ms 5068 KB Output is correct
47 Correct 6 ms 5080 KB Output is correct
48 Correct 6 ms 5088 KB Output is correct
49 Correct 6 ms 5068 KB Output is correct
50 Correct 6 ms 5068 KB Output is correct
51 Correct 6 ms 5068 KB Output is correct
52 Correct 6 ms 5068 KB Output is correct
53 Correct 8 ms 5068 KB Output is correct
54 Correct 7 ms 5068 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 1709 ms 13424 KB Output is correct
4 Execution timed out 2056 ms 16304 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4944 KB Output is correct
7 Correct 3 ms 4944 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 5068 KB Output is correct
10 Correct 3 ms 5068 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 4940 KB Output is correct
16 Correct 3 ms 4996 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 3 ms 5068 KB Output is correct
19 Correct 3 ms 4944 KB Output is correct
20 Correct 3 ms 5068 KB Output is correct
21 Correct 3 ms 4940 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 3 ms 4940 KB Output is correct
24 Correct 4 ms 5068 KB Output is correct
25 Correct 3 ms 4940 KB Output is correct
26 Correct 3 ms 4944 KB Output is correct
27 Correct 3 ms 5004 KB Output is correct
28 Correct 3 ms 5068 KB Output is correct
29 Correct 1709 ms 13424 KB Output is correct
30 Execution timed out 2056 ms 16304 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4944 KB Output is correct
7 Correct 3 ms 4944 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 5068 KB Output is correct
10 Correct 3 ms 5068 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 4940 KB Output is correct
16 Correct 3 ms 4996 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 3 ms 5068 KB Output is correct
19 Correct 3 ms 4944 KB Output is correct
20 Correct 3 ms 5068 KB Output is correct
21 Correct 3 ms 4940 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 3 ms 4940 KB Output is correct
24 Correct 4 ms 5068 KB Output is correct
25 Correct 3 ms 4940 KB Output is correct
26 Correct 3 ms 4944 KB Output is correct
27 Correct 3 ms 5004 KB Output is correct
28 Correct 3 ms 5068 KB Output is correct
29 Correct 7 ms 5068 KB Output is correct
30 Correct 6 ms 5172 KB Output is correct
31 Correct 6 ms 5068 KB Output is correct
32 Correct 5 ms 5068 KB Output is correct
33 Correct 5 ms 5068 KB Output is correct
34 Correct 6 ms 5068 KB Output is correct
35 Correct 7 ms 5068 KB Output is correct
36 Correct 6 ms 5068 KB Output is correct
37 Correct 10 ms 5284 KB Output is correct
38 Correct 10 ms 5152 KB Output is correct
39 Correct 7 ms 5196 KB Output is correct
40 Correct 6 ms 5068 KB Output is correct
41 Correct 6 ms 5068 KB Output is correct
42 Correct 7 ms 5068 KB Output is correct
43 Correct 5 ms 5068 KB Output is correct
44 Correct 5 ms 5068 KB Output is correct
45 Correct 5 ms 5068 KB Output is correct
46 Correct 6 ms 5068 KB Output is correct
47 Correct 6 ms 5080 KB Output is correct
48 Correct 6 ms 5088 KB Output is correct
49 Correct 6 ms 5068 KB Output is correct
50 Correct 6 ms 5068 KB Output is correct
51 Correct 6 ms 5068 KB Output is correct
52 Correct 6 ms 5068 KB Output is correct
53 Correct 8 ms 5068 KB Output is correct
54 Correct 7 ms 5068 KB Output is correct
55 Execution timed out 2082 ms 11300 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 5008 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4944 KB Output is correct
7 Correct 3 ms 4944 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 5068 KB Output is correct
10 Correct 3 ms 5068 KB Output is correct
11 Correct 3 ms 4940 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 4 ms 4940 KB Output is correct
14 Correct 3 ms 4940 KB Output is correct
15 Correct 4 ms 4940 KB Output is correct
16 Correct 3 ms 4996 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 3 ms 5068 KB Output is correct
19 Correct 3 ms 4944 KB Output is correct
20 Correct 3 ms 5068 KB Output is correct
21 Correct 3 ms 4940 KB Output is correct
22 Correct 4 ms 4940 KB Output is correct
23 Correct 3 ms 4940 KB Output is correct
24 Correct 4 ms 5068 KB Output is correct
25 Correct 3 ms 4940 KB Output is correct
26 Correct 3 ms 4944 KB Output is correct
27 Correct 3 ms 5004 KB Output is correct
28 Correct 3 ms 5068 KB Output is correct
29 Correct 7 ms 5068 KB Output is correct
30 Correct 6 ms 5172 KB Output is correct
31 Correct 6 ms 5068 KB Output is correct
32 Correct 5 ms 5068 KB Output is correct
33 Correct 5 ms 5068 KB Output is correct
34 Correct 6 ms 5068 KB Output is correct
35 Correct 7 ms 5068 KB Output is correct
36 Correct 6 ms 5068 KB Output is correct
37 Correct 10 ms 5284 KB Output is correct
38 Correct 10 ms 5152 KB Output is correct
39 Correct 7 ms 5196 KB Output is correct
40 Correct 6 ms 5068 KB Output is correct
41 Correct 6 ms 5068 KB Output is correct
42 Correct 7 ms 5068 KB Output is correct
43 Correct 5 ms 5068 KB Output is correct
44 Correct 5 ms 5068 KB Output is correct
45 Correct 5 ms 5068 KB Output is correct
46 Correct 6 ms 5068 KB Output is correct
47 Correct 6 ms 5080 KB Output is correct
48 Correct 6 ms 5088 KB Output is correct
49 Correct 6 ms 5068 KB Output is correct
50 Correct 6 ms 5068 KB Output is correct
51 Correct 6 ms 5068 KB Output is correct
52 Correct 6 ms 5068 KB Output is correct
53 Correct 8 ms 5068 KB Output is correct
54 Correct 7 ms 5068 KB Output is correct
55 Correct 1709 ms 13424 KB Output is correct
56 Execution timed out 2056 ms 16304 KB Time limit exceeded
57 Halted 0 ms 0 KB -