Submission #1133002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133002		Hamed_Ghaffari	Joker (BOI20_joker)	C++20	100 / 100	134 ms	6844 KiB

Joker

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,sse4,sse4.2,lzcnt,popcnt")

using pii = pair<int, int>;

#define pb push_back

const int MXN = 2e5+5;

struct DSU {
  int par[MXN], sz[MXN];
  bool val[MXN];
  vector<pii> his;
  DSU() {
    iota(par, par+MXN, 0);
    fill(sz, sz+MXN, 1);
  }
  int root(int v) { return v==par[v] ? v : root(par[v]); }
  bool side(int v) { return v==par[v] ? 0 : side(par[v])^val[v]; }
  bool can(int u, int v) {
    int ru = root(u), rv = root(v);
    if(ru!=rv) return 1;
    return side(u)!=side(v);
  }
  void con(int u, int v) {
    int ru = root(u), rv = root(v);
    if(ru==rv) {
      his.pb(pii(-1, -1));
      return;
    }
    if(sz[ru]<sz[rv]) swap(u,v), swap(ru, rv);
    val[rv] = side(u)==side(v);
    par[rv] = ru;
    sz[ru] += sz[rv];
    his.pb(pii(ru, rv));
  }
  void undo() {
    assert(!his.empty());
    auto [u, v] = his.back();
    his.pop_back();
    if(u==-1) return;
    val[v] = 0;
    par[v] = v;
    sz[u] -= sz[v];
  }
  void clear() { while(!his.empty()) undo(); }
} dsu;

int n, m, q, U[MXN], V[MXN], dp[MXN];

void divide(int l, int r, int opl, int opr) {
  if(l>r) return;
  int mid = l+r>>1;
  for(int i=l; i<=mid; i++) dsu.con(U[i], V[i]);
  for(int i=opr; i>=opl; i--) {
    if(!dsu.can(U[i], V[i])) break;
    dp[mid]=i;
    dsu.con(U[i], V[i]);
  }
  for(int i=opr; i>=dp[mid]; i--) dsu.undo();
  divide(mid+1, r, dp[mid], opr);
  for(int i=l; i<=mid; i++) dsu.undo();
  for(int i=dp[mid]+1; i<=opr; i++) dsu.con(U[i], V[i]);
  divide(l, mid-1, opl, dp[mid]);
  for(int i=dp[mid]+1; i<=opr; i++) dsu.undo();
}

int32_t main() {
  cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  cin >> n >> m >> q;
  for(int i=1; i<=m; i++)
    cin >> U[i] >> V[i];
  U[m+1] = 0;
  V[m+1] = 1;
  int pre=0;
  for(int i=1; i<=m+1; i++) {
    if(!dsu.can(U[i], V[i])) break;
    pre=i;
    dsu.con(U[i], V[i]);
  }
  dsu.clear();
  fill(dp+1, dp+m+2, m+2);
  for(int i=m+1; i>=1; i--) {
    if(!dsu.can(U[i], V[i])) break;
    dp[0]=i;
    dsu.con(U[i], V[i]);
  }
  dsu.clear();
  if(pre==m+1) {
    while(q--) {
      int l, r;
      cin >> l >> r;
      cout << "NO\n";
    }
    return 0;
  }
  divide(1, pre, 1, m+1);
  while(q--) {
    int l, r;
    cin >> l >> r;
    cout << (dp[l-1]<=r+1 ? "NO" : "YES") << '\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