Submission #1094937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094937		ntdaccode	Joker (BOI20_joker)	C++17	0 / 100	239 ms	22408 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(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)
{
  if(l1>l2) return ;
  int mid=(l1+l2)/2;
  //cout << mid << "\n";
//  if(mid==7)
//  {
////    cout << l1 << " " << l2 << " " << r1 << " " << r2 << "\n";
//     // fori(i,1,n) cout << id[i] << " ";
//  }
  bool ok=0;
  fori(i,l1,mid-1)
  {
    if(unioned(x[i],y[i],mid,0)) ok=1;
  }
  //cout << ok << " ";
  int opt=r2+1;
  if(!ok)
  for(int i=r2;i>=r1;i--)
  {
    if(unioned(x[i],y[i],mid,1)) ok=1;
    //if(mid==7) cout << i << " ";
    if(ok)
    {
      opt=i;
      break;
    }
  }
  //cout << opt << " ";
  if(ok) last[mid]=opt;
  //return ;
  rollback(1,mid);
  unioned(x[mid],y[mid],mid,0);
  solve(mid+1,l2,opt,r2);
  for(int i=r2;i>=opt;i--) unioned(x[i],y[i],mid,1);
  rollback(0,mid);
  solve(l1,mid-1,r1,opt-1);
  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);
  //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:104:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:105:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |     freopen(task".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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