oj.uz

Submission #733840

# Submission time Handle Problem Language Result Execution time Memory
733840 2023-05-01T11:05:42 Z MilosMilutinovic Joker (BOI20_joker) C++14
0 / 100
 420 ms 14856 KB 
/**
 *    author:  wxhtzdy
 *    created: 01.05.2023 11:39:02
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, m, q;
  cin >> n >> m >> q;
  vector<int> u(m), v(m);
  for (int i = 0; i < m; i++) {
    cin >> u[i] >> v[i];
    --u[i]; --v[i];
  }
  vector<int> pr(n), sz(n, 1), col(n);
  iota(pr.begin(), pr.end(), 0);
  bool bad = false;
  vector<tuple<int, int, bool, int, int, int, int>> stk;
  function<pair<int, int>(int)> root = [&](int x) {
    if (pr[x] == x) {
      return make_pair(x, col[x]);
    } else {
      auto p = root(pr[x]);
      return make_pair(p.first, col[x] ^ p.second);
    }
  };
  function<void(int, int)> Unite = [&](int x, int y) {
    assert(x != y);
    pair<int, int> xs = root(x);
    pair<int, int> ys = root(y);
    x = xs.first;
    y = ys.first;
    stk.emplace_back(x, y, bad, sz[x], sz[y], col[x], col[y]);
    if (x == y) {
      if (xs.second == ys.second) {
        bad = true;
      }  
    } else {
      if (sz[x] < sz[y]) {
        swap(x, y); 
      }
      sz[x] += sz[y];
      pr[y] = x;
      col[y] = (1 ^ col[x] ^ col[y]);
    }
  };
  auto Rollback = [&]() {
    auto op = stk.back();
    stk.pop_back();
    int x = get<0>(op);
    int y = get<1>(op);
    pr[x] = x;
    pr[y] = y;
    bad = get<2>(op);
    sz[x] = get<3>(op);
    sz[y] = get<4>(op);
    col[x] = get<5>(op);
    col[y] = get<6>(op);
  };
  for (int i = 0; i < m; i++) {
    Unite(u[i], v[i]);
  }        
  if (!bad) {
    while (q--) {
      int l, r;
      cin >> l >> r;
      --l; --r;
      cout << "NO" << '\n';
    }
    return 0;
  }
  for (int i = 0; i < m; i++) {
    Rollback();
  }     
  vector<int> f(m);
  function<void(int, int, int)> Solve = [&](int l, int r, int rr) {
    if (l > r) {
      return;
    }
    int mid = l + r >> 1;    
    for (int i = l; i < mid; i++) {
      Unite(u[i], v[i]);
    }
    f[mid] = rr;
    if (!bad) {
      for (int i = rr - 1; i >= mid; i--) {
        Unite(u[i], v[i]);
        f[mid] = i;
        if (bad) {
          break;  
        }
      }
      for (int i = f[mid]; i < rr; i++) {
        Rollback();
      }
    }
    for (int i = l; i < mid; i++) {
      Rollback();
    }    
    {         
      for (int i = f[mid]; i < rr; i++) {
        Unite(u[i], v[i]);
      }
      Solve(l, mid - 1, f[mid]);
      for (int i = f[mid]; i < rr; i++) {
        Rollback();
      }
    }
    {
      for (int i = l; i <= mid - (mid == rr); i++) {
        Unite(u[i], v[i]);
      }
      Solve(mid + 1, r, rr);  
      for (int i = l; i <= mid - (mid == rr); i++) {
        Rollback();
      }
    }
  };
  Solve(0, m - 1, m);       
  while (q--) {
    int l, r;
    cin >> l >> r;
    --l; --r;
    cout << (f[l] > r ? "YES" : "NO") << '\n';
  }
  return 0;
}

Compilation message

Joker.cpp: In lambda function:
Joker.cpp:84:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 342 ms 10316 KB Output is correct
4 Incorrect 420 ms 14856 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -