Submission #1283485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283485		repmann	Joker (BOI20_joker)	C++20	100 / 100	171 ms	9480 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
int N, M, K, Q;
int U[200001], V[200001];
int O[200001];
struct Node
{
  int p, r;
  bool w;
}DSU[200001];
bool bipartite;
struct Delta
{
  int i;
  Node u;
}D[400001];
int d;
inline void Rollback(int d0)
{
  while(d > d0)
  {
    if(D[d].i) DSU[D[d].i] = D[d].u;
    else bipartite = 1;
    d--;
  }
  return;
}
inline int Find(int u)
{
  while(u != DSU[u].p) u = DSU[u].p;
  return u;
}
inline bool Path(int u)
{
  bool w = 0;
  while(u != DSU[u].p) {w ^= DSU[u].w; u = DSU[u].p;}
  return w;
}
inline void Union(int u, int v)
{
  bool uw = Path(u);
  u = Find(u);
  bool vw = Path(v);
  v = Find(v);
  if(u == v)
  {
    if(bipartite && (uw == vw)) {D[++d] = {0, DSU[0]}; bipartite = 0;}
    return;
  }
  if(DSU[u].r < DSU[v].r) swap(u, v);
  if(DSU[u].r == DSU[v].r)
  {
    D[++d] = {u, DSU[u]};
    DSU[u].r++;
  }
  D[++d] = {v, DSU[v]};
  DSU[v].p = u;
  DSU[v].w = uw ^ vw ^ 1;
  return;
}
inline void DC(int L1, int R1, int L2, int R2)
{
//  cout << L1 << ' ' << R1 << ' ' << L2 << ' ' << R2 << '\n';
  int S = (L1 + R1) >> 1;
  int dL = d;
  for(int i = L1; i < S; i++) Union(U[i], V[i]);
  int dR = d;
//  cout << bipartite << '\n';
  for(O[S] = R2; (O[S] >= S) && bipartite; O[S]--) Union(U[O[S] - 1], V[O[S] - 1]);
//  cout << bipartite << '\n';
//  cout << S << ' ' << O[S] << '\n';
  Rollback(dR);
  if(S < R1)
  {
    Union(U[S], V[S]);
    DC(S + 1, R1, O[S], R2);
  }
  Rollback(dL);
  if(L1 < S)
  {
    int dOS = d;
    for(int i = R2 - 1; i >= O[S]; i--) Union(U[i], V[i]);
    DC(L1, S - 1, L2, O[S]);
    Rollback(dOS);
  }
  return;
}
int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> N >> M >> Q;
  for(int i = 1; i <= M; i++) cin >> U[i] >> V[i];
  d = 0;
  bipartite = 1;
  for(int i = 1; i <= N; i++) DSU[i] = {i, 0, 0};
  DC(1, M, 1, M + 1);
//  for(int i = 1; i <= M; i++) cout << i << ": " << O[i] << '\n';
  int l, r;
  for(int i = 1; i <= Q; i++)
  {
    cin >> l >> r;
    if((r + 1) <= O[l]) cout << "YES\n";
    else cout << "NO\n";
  }

  return 0;
}

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