Submission #1094955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094955		ntdaccode	Joker (BOI20_joker)	C++17	100 / 100	245 ms	24132 KiB

Joker

#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod=1e9+7;
const int M=1e6+10;
const int N=1e3+10;
int n,m,q;
int x[M],y[M];
//
int id[M],lz[M];
int finded(int u,int &v)
{
  v^=lz[u];
  return id[u]<0 ? u : finded(id[u],v);
}
#define tp tuple<int,int,int>
stack<tp> sk[2];
stack<tp> ks[2];
bool unioned(int u,int v,int mid,int tt)
{
  int x=0;
  int y=0;
  u=finded(u,x);
  v=finded(v,y);
  //if(mid==6) cout << u << " " << v << " " << x << " " << y << "\n";
  if(u==v)
  {
    if(x==y) return true;
    return false;
  }
  if(id[u]>id[v]) swap(u,v);
  sk[tt].push({u,v,mid});
  ks[tt].push({id[u],id[v],lz[v]});
  id[u]+=id[v]; id[v]=u; if(x==y) lz[v]^=1;
  return false;
}
void rollback(int tt,int midl)
{
    while(sk[tt].size())
    {
      auto[u,v,mid]=sk[tt].top();
      if(mid!=midl) break;
      sk[tt].pop();
      auto[idu,idv,lzz]=ks[tt].top();
      ks[tt].pop();
      id[u]=idu;
      id[v]=idv;
      lz[v]=lzz;
    }
}
//
int last[M];
void solve(int l1,int l2,int r1,int r2,bool okk)
{
  if(l1>l2) return ;
  int mid=(l1+l2)/2;
  bool ok=okk;
//      cout << mid << "\n";
//    cout << l1 << " " << l2 << " " << r1 << " " << r2  << " " << sk[1].size() <<  "\n";
//      fori(i,1,n) cout << id[i] << " ";
//      cout << endl;

  fori(i,l1,mid-1)
  {
    if(unioned(x[i],y[i],mid,0)) ok=1;
  }
  bool tmpok=ok;
  int opt=r2;
  if(!ok)
  for(int i=r2;i>=max(r1,mid);i--)
  {
    if(unioned(x[i],y[i],mid,1)) ok=1;
    if(ok)
    {
      opt=i;
      break;
    }
  }
  if(ok) last[mid]=(tmpok&&r2==m ? m+1 : opt);
//    cout << mid << "\n";
//    cout << okk << " " << l1 << " " << l2 << " " << r1 << " " << r2 << " " << last[mid] <<  "\n";
//      fori(i,1,n) cout << id[i] << " ";
//      cout << endl;

  if(l1!=l2)
  {
  rollback(1,mid);
  if(unioned(x[mid],y[mid],mid,0)) tmpok=1;
  solve(mid+1,l2,opt,r2,tmpok);
  ok=okk;
  rollback(0,mid);
  for(int i=r2;i>opt;i--)
  {
    if( unioned(x[i],y[i],mid,1)) ok=1;
  }
  solve(l1,mid-1,r1,opt,ok);
  }
  rollback(1,mid);
}
int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  #define task "1"
  if(fopen(task".inp","r"))
  {
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);
  }
  cin >> n >> m >> q;
  fori(i,1,m) cin >> x[i] >> y[i];
  fori(i,1,n) id[i]=last[i]=-1;
  solve(1,m,1,m,0);
  //fori(i,1,n) cout << last[i] << " ";
  while(q--)
  {
    int l,r;
    cin >> l >> r;
    if(r<last[l]) cout << "YES\n";
    else cout << "NO\n";
  }
}

Compilation message (stderr)

Joker.cpp: In function 'int32_t main()':
Joker.cpp:113:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:114:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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