oj.uz

Submission #660117

# Submission time Handle Problem Language Result Execution time Memory
660117 2022-11-20T11:38:53 Z jamezzz Joker (BOI20_joker) C++17
0 / 100
 98 ms 15140 KB 
#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(){
	//pf("undo\n");
	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]);
	//pf("tryjoin: %d, %d %d, %d %d, %d %d\n",i,u[i],v[i],cu,cv,pu,pv);
	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=optr;i>far[m];--i)undo();
	for(int i=m;i>=l;--i)if(joined[i])undo();
	for(int i=optr;i>far[m];--i)tryjoin(i);
	dnc(l,m-1,optl,far[m]);
	for(int i=optr;i>far[m];--i)if(joined[i])undo();
	for(int i=l;i<=m;++i)tryjoin(i);
	dnc(m+1,r,max(far[m],m+1),optr);
	for(int i=l;i<=m;++i)if(joined[i])undo();
}

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;
	}
	//>lst is autowin
	for(int i=1;i<=lst;++i){
		if(joined[i])undo();
	}
	far[0]=m+1;
	for(int i=m;i>=1;--i){
		if(tryjoin(i))far[0]=i;
		else break;
	}
	for(int i=m;i>=far[0];--i){
		if(joined[i])undo();
	}
	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

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:112:13: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   int l,r;sf("%d%d",&l,&r);
      |             ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Runtime error 98 ms 15140 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -