Submission #1175628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175628		sasde	Joker (BOI20_joker)	C++20	100 / 100	246 ms	9956 KiB

Joker

#include<bits/stdc++.h>
#define task "odd"
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back
#define emb emplace_back
#define emf emplace_front
#define em emplace
using namespace std;
const int N=1e6+5,lg=20,mod=1e9+7;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int u,int v){
 return u+rd()%(v-u+1);
}
int n,m,q,rk[N];
 bool haiphia=true;
 ii r[N]; 
 struct rolback
 {
 int u,rku,v,rkv,haiphia; 
 };
 vector<rolback>quay;
 void re(){
  for(int i=1;i<=n;++i)r[i]={i,0};
 };
 ii acs(int u){
  if(r[u].fi==u)return {u,0};
  ii x=acs(r[u].fi);
  return {x.fi,x.se^r[u].se};
 }
 bool join(int u,int v){
     ii a=acs(u);
     u=a.fi;
     int x=a.se;
     ii b=acs(v);
     v=b.fi;
     int y=b.se;
     // cout <<u<<" "<<v<<" "<<a.fi<<" "<<b.fi<<" "<<a.se<<" "<<b.se<<'\n';
     if(u==v){
      if(x==y){
        quay.pb({u,rk[u],v,rk[v],haiphia});
        haiphia=false;
        return true;
      }
      return false;
     }
      if(rk[v]>rk[u])swap(u,v);
      quay.pb({u,rk[u],v,rk[v],haiphia});
      r[v]={u,x^y^1};
      rk[u]+=(r[u]==r[v]);
 return true;
 }
 void rollback(){
  if(quay.empty())return;
  rolback x=quay.back();quay.pop_back();
  r[x.u]={x.u,0};
  r[x.v]={x.v,0};
  rk[x.u]=x.rku;
  rk[x.v]=x.rkv;
  haiphia=x.haiphia;
 }
ii b[N];
int last[N];
bool nho[N];
void kiemtra(){
  for(int i=1;i<=m;++i){
    join(b[i].fi,b[i].se);
  }
  if(haiphia){
  for(int i=1;i<=q;++i)cout <<"NO\n";
  exit(0);
  }
  while(!quay.empty())rollback();
}
void dnc(int l1,int l2,int r1,int r2){
  int mid=(l1+l2)>>1;
  for(int i=l1;i<=mid;++i)nho[i]=join(b[i].fi,b[i].se);
  int p=r1;
  for(int i=r2;i>=r1;--i){
    nho[i]=join(b[i].fi,b[i].se);
    if(!haiphia){
      p=i+1;
      break;  
    }
  }
  for(int i=p-1;i<=r2;++i)if(nho[i])rollback();
  last[mid]=p;
  for(int i=l1;i<=mid;++i)if(nho[i])rollback();
  for(int i=r2;i>=p+1;--i)nho[i]=join(b[i].fi,b[i].se);
  if(mid>l1)dnc(l1,mid-1,r1,p);
  for(int i=r2;i>=p+1;--i)if(nho[i])rollback();
  for(int i=l1;i<=mid;++i)nho[i]=join(b[i].fi,b[i].se);
  if(mid<l2)dnc(mid+1,l2,p-1,r2);
  for(int i=l1;i<=mid;++i)if(nho[i])rollback();

}
void solve(){
  cin >> n >> m >> q;
  for(int i=1;i<=m;++i)cin >> b[i].fi>> b[i].se;
  for(int i=1;i<=n;++i)r[i]={i,0}; 
  // s.re();
    // rollback();
    kiemtra();
    int p=m;
    join(b[m].fi,b[m].se);
    for(int i=1;i<=m;++i){
       join(b[i].fi,b[i].se);
       if(!haiphia){
        p=i-1;
        break;
       }
    }
    for(int i=p+1;i<=m;++i)last[i]=m+1;
    while(!quay.empty())rollback();
    dnc(1,p,1,m);
    while(!quay.empty())rollback();p=m+1;
    for(int i=1;i<=m;++i){
      join(b[i].fi,b[i].se);
      if(!haiphia){
        p=i;
        break;
      }
    }
    while(!quay.empty())rollback();
    for(int i=p;i<=m;++i)last[i]=1e9;
    last[0]=1e9;
    for(int i=m;i>=1;--i){
      join(b[i].fi,b[i].se);
      if(!haiphia){
        last[0]=i+1;
        break;
      }
    }
    for(int i=1;i<=q;++i){
      int l,r;
      cin >> l >> r;
      if(last[l-1]<=r+1)cout <<"NO\n";
      else cout <<"YES\n";
    }
}
main()
{
  srand(time(0));
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    if(fopen(task".inp","r")){
      freopen(task".inp","r",stdin);
      freopen(task".out","w",stdout);
    }
    int t=1;
 //   cin >> t;
while(t--){
    solve();
    // cout<<'\n';
}

}

Compilation message (stderr)

Joker.cpp:150:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  150 | main()
      | ^~~~
Joker.cpp: In function 'int main()':
Joker.cpp:157:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:158:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |       freopen(task".out","w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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