제출 #1207781

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1207781		pudelos	Joker (BOI20_joker)	C++20	100 / 100	324 ms	17512 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, a, b) for(int i=a; i<=b; ++i)
#define FORB(i, a, b) for(int i=a; i>=b; --i)
#define sz(A) (int)(A.size())
#define eb emplace_back
#define pb push_back
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
#define rs resize
#define V vector

int n, m, q;
V<pi> kraw;
V<int> dp;

struct Fu {
  V<int> rep, A, sajs;
  set<int> secik;
  V<pair<int, pi>> stosik;
  void init() {
    rep.rs(n+1);
    A.rs(n+1);
    sajs.rs(n+1);
    FOR(i, 1, n) {
      rep[i]=i;
      sajs[i]=1;
    }
  }

  int ff(int x) {
    if(rep[x]==x) return x;
    return ff(rep[x]);
  }

  int odl(int x) {
    int sum=0;
    while(rep[x]!=x) sum^=A[x], x=rep[x];
    sum^=A[x];
    return sum;
  }

  void uu(int id) {
    auto [aq, bq] = kraw[id];
    int a=ff(aq);
    int b=ff(bq);
    if(a==b) {
      if((odl(aq)^odl(bq))==0) {
        secik.insert(id);
        stosik.pb({-1, {id, 0}});
      } else {
        stosik.pb({-1, {id, 0}});
      }
      return;
    }
    if(sajs[a]<sajs[b]) swap(a, b);

    int oldas = sajs[a];
    rep[b]=a;
    sajs[a]+=sajs[b];
    int zmiana=0;
    if((odl(aq)^odl(bq))==0) A[b]^=1, zmiana=1;
    stosik.pb({b, {zmiana, oldas}});
  }

  void rollback() {
    auto [a, dane] = stosik.back();
    auto [b, c] = dane;
    stosik.pop_back();
    if(a==-1) {
      if(secik.find(b)!=secik.end()) secik.erase(b);
      return;
    }
    sajs[rep[a]]=c;
    rep[a]=a;
    A[a]^=b;
  }

  bool cykl_np() {
    return (sz(secik)>=1);
  }
} AF;

void rozw(int l1, int l2, int r1, int r2) {
  if(l1>l2) return;
  int mid = (l1+l2)/2;
  FOR(i, l1, mid-1) AF.uu(i);
  int w=-1;
  if(AF.cykl_np()) w=r2;
  else {
    int ile=0;
    FORB(i, r2, max(mid, r1)) {
      AF.uu(i);
      ++ile;
      if(AF.cykl_np()) {
        w=i-1;
        break;
      }
    }
    FOR(i, 1, ile) AF.rollback();
  }
  
  if(l1==l2) {
    FORB(i, mid-1, l1) AF.rollback();
    dp[l1]=w;
    return;
  }
  AF.uu(mid);
  rozw(mid+1, l2, max(w, r1), r2);
  AF.rollback();

  FORB(i, mid-1, l1) AF.rollback();
  FORB(i, r2, max(w+1, r1)) AF.uu(i);
  rozw(l1, mid, r1, min(w, r2));
  FOR(i, max(w+1, r1), r2) AF.rollback();
}

signed main() {
  cin.tie(0) -> ios_base::sync_with_stdio(0);
  cin >> n >> m >> q;
  kraw.rs(m+1);
  dp.rs(m+1);
  int a, b;
  FOR(i, 1, m) {
    cin >> a >> b;
    kraw[i]={a, b};
  }

  AF.init();
  FOR(i, 1, m) AF.uu(i);
  if(!AF.cykl_np()) {
    FOR(i, 1, q) cout << "NO\n";
    exit(0);
  }
  FOR(i, 1, m) AF.rollback();
  rozw(1, m, 1, m);

  FOR(i, 1, q) {
    cin >> a >> b;
    if(b<=dp[a]) cout << "YES\n";
    else cout << "NO\n";
  }
}

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