Submission #660124

#	Time	Username	Problem	Language	Result	Execution time	Memory
660124		jamezzz	Joker (BOI20_joker)	C++17	100 / 100	306 ms	14928 KiB

Joker

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define sf scanf
#define pf printf
#define pb push_back
typedef pair<int,int> ii;

#define maxn 200005

int n,m,M,q,u[maxn],v[maxn],far[maxn],joined[maxn];
int par[maxn],rnk[maxn],flip[maxn];
vector<pair<ii,ii>> hist;

int fp(int i){
	while(par[i]!=i)i=par[i];
	return i;
}

int col(int i){
	int res=0;
	while(par[i]!=i)res^=flip[i],i=par[i];
	return res;
}

bool join(int x,int y,bool f){
	x=fp(x),y=fp(y);
	if(x==y)return false;
	if(rnk[x]<rnk[y])swap(x,y);
	hist.pb({{x,rnk[x]},{y,rnk[y]}});
	par[y]=x;
	if(rnk[x]==rnk[y])++rnk[x];
	if(f)flip[y]=true;
	return true;
}

void undo(int i){
	if(!joined[i])return;
	joined[i]=false;
	assert(!hist.empty());
	auto[x,rx]=hist.back().fi;
	auto[y,ry]=hist.back().se;
	hist.pop_back();
	par[x]=x;par[y]=y;
	rnk[x]=rx;rnk[y]=ry;
	flip[x]=flip[y]=false;
}

bool tryjoin(int i){
	int cu=col(u[i]),cv=col(v[i]);
	int pu=fp(u[i]),pv=fp(v[i]);
	if(pu==pv&&cu==cv)return false;
	joined[i]=join(u[i],v[i],cu==cv);
	return true;
}

void dnc(int l,int r,int optl,int optr){
	//pf("dnc: %d %d, %d %d\n",l,r,optl,optr);
	if(l>r||optl>optr)return;
	int m=(l+r)>>1;
	//try to find answer for m
	for(int i=l;i<=m;++i)tryjoin(i);
	//find first pos that will win
	for(int i=optr;i>=optl;--i){
		if(!tryjoin(i)){
			far[m]=i;
			break;
		}
	}
	//pf("far %d: %d\n",m,far[m]);
	for(int i=far[m]+1;i<=optr;++i)undo(i);
	for(int i=m;i>=l;--i)undo(i);
	for(int i=optr;i>far[m];--i)tryjoin(i);
	dnc(l,m-1,optl,far[m]);
	for(int i=far[m]+1;i<=optr;++i)undo(i);
	for(int i=l;i<=m;++i)tryjoin(i);
	dnc(m+1,r,max(far[m],m+1),optr);
	for(int i=m;i>=l;--i)undo(i);
}

int main(){
	sf("%d%d%d",&n,&m,&q);
	M=m;
	for(int i=1;i<=m;++i){
		sf("%d%d",&u[i],&v[i]);
	}
	for(int i=1;i<=n;++i){
		par[i]=i,rnk[i]=0,flip[i]=0;
	}
	for(int i=1;i<=m;++i)far[i]=m+1;
	int lst=-1;
	for(int i=1;i<=m;++i){
		if(!tryjoin(i))break;
		lst=i;
	}
	for(int i=1;i<=lst;++i)far[i]=-1;
	//>lst is autowin
	for(int i=lst;i>=1;--i)undo(i);
	far[0]=0;
	for(int i=m;i>=1;--i){
		if(!tryjoin(i)){
			far[0]=i;
			break;
		}
	}
	for(int i=far[0]+1;i<=m;++i)undo(i);
	dnc(1,lst,1,m);
	for(int i=0;i<q;++i){
		int l,r;sf("%d%d",&l,&r);
		if(r>=far[l-1])pf("NO\n");
		else pf("YES\n");
	}
}

Compilation message (stderr)

Joker.cpp: In function 'int main()':
Joker.cpp:84:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |  sf("%d%d%d",&n,&m,&q);
      |    ^
Joker.cpp:87:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |   sf("%d%d",&u[i],&v[i]);
      |     ^
Joker.cpp:111:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |   int l,r;sf("%d%d",&l,&r);
      |             ^

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