oj.uz

Submission #1093491

# Submission time Handle Problem Language Result Execution time Memory
1093491 2024-09-27T01:18:14 Z duckindog Joker (BOI20_joker) C++17
25 / 100
 271 ms 13236 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10;
int n, m, q;
struct Edge { 
  int u, v;
  friend istream& operator >> (istream& is, auto& rhs) { 
    return is >> rhs.u >> rhs.v;
  }
} edge[N];

int id[N], cnt;
bool mk[N];
vector<tuple<int, int, int, int, int, int>> undo;
int root(int u) { return id[u] < 0 ? u : root(id[u]); }
bool chk(int u) { return id[u] < 0 ? mk[u] : mk[u] ^ chk(id[u]); }
void add(int u, int v) { 
  int oU = u, oV = v;
  u = root(u); v = root(v);
  if (u == v) { 
    undo.emplace_back(0, 0, 0, 0, 0, cnt);
    cnt += chk(oU) == chk(oV);
    return;
  }
  
  if (id[u] > id[v]) swap(u, v);
  undo.emplace_back(u, id[u], v, id[v], mk[v], cnt);

  mk[v] ^= (chk(oU) == chk(oV));
  id[u] += id[v];
  id[v] = u;
}
void rollBack() { 
  auto [u, idU, v, idV, mkV, pCnt] = undo.back(); undo.pop_back();
  id[u] = idU;
  id[v] = idV;
  mk[v] = mkV;
  cnt = pCnt;
}

int f[N];
void dnc(int l, int r, int lt, int rt) { 
  if (l > r) return;
  int mid = (l + r) >> 1;
  auto& ret = f[mid];

  for (int i = l; i < mid; ++i) add(edge[i].u, edge[i].v);
  for (int i = rt; i >= max(mid + 1, lt); --i) add(edge[i].u, edge[i].v);

  for (int i = max(mid + 1, lt); i <= rt; ++i) { 
    if (cnt) ret = i - 1;
    rollBack();
  } if (cnt) ret = rt;
  
  int nxtR = (!ret ? max(mid + 1, lt) : ret),
      nxtL = (!ret ? mid : ret);

  add(edge[mid].u, edge[mid].v);
  dnc(mid + 1, r, nxtR, rt);
  for (int i = mid; i >= l; --i) rollBack();

  for (int i = rt; i > nxtL; --i) add(edge[i].u, edge[i].v);
  dnc(l, mid - 1, lt, nxtL);
  for (int i = rt; i > nxtL; --i) rollBack();
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m >> q;
  for (int i = 1; i <= m; ++i) cin >> edge[i];

  memset(id, -1, sizeof id);
  dnc(1, n, 1, m);

  while (q--) { 
    int l, r; cin >> l >> r;
    cout << (r <= f[l] ? "YES" : "NO") << "\n";
  }
}

Compilation message

Joker.cpp:9:45: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    9 |   friend istream& operator >> (istream& is, auto& rhs) {
      |                                             ^~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 0 ms 1116 KB Output is correct
4 Incorrect 1 ms 1116 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 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 0 ms 1116 KB Output is correct
4 Incorrect 1 ms 1116 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 127 ms 12592 KB Output is correct
4 Correct 164 ms 11968 KB Output is correct
5 Correct 172 ms 13232 KB Output is correct
6 Correct 159 ms 12724 KB Output is correct
7 Correct 180 ms 12720 KB Output is correct
8 Correct 179 ms 11956 KB Output is correct
9 Correct 203 ms 12096 KB Output is correct
10 Correct 269 ms 12720 KB Output is correct
11 Correct 175 ms 12468 KB Output is correct
12 Correct 212 ms 13236 KB Output is correct
13 Correct 168 ms 12212 KB Output is correct
14 Correct 186 ms 12468 KB Output is correct
15 Correct 238 ms 12728 KB Output is correct
16 Correct 271 ms 13232 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 0 ms 1116 KB Output is correct
4 Incorrect 1 ms 1116 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 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 0 ms 1116 KB Output is correct
4 Incorrect 1 ms 1116 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 1112 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 0 ms 1116 KB Output is correct
4 Incorrect 1 ms 1116 KB Output isn't correct
5 Halted 0 ms 0 KB -