Submission #907407

#	Time	Username	Problem	Language	Result	Execution time	Memory
907407		sunwukong123	Joker (BOI20_joker)	C++14	100 / 100	225 ms	31060 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MAXN = 200005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
int n,m,q;
pi E[MAXN];
int ans[MAXN];//suppose [1,i] is blocked, what is the minimum r such that the answer is yes?
struct ufds_{
	vector<array<int,4>> rb;
	pi par[MAXN];
	int sz[MAXN];
	bool bad=0;
	ufds_(){
		fill(sz,sz+MAXN,1);
		for(int i=0;i<MAXN;i++){
			par[i]=pi(i,0);
		}
	}
	pi find(int x){ // NO PATH COMPRESSION IN ROLLBACKS!!!
		int OFF=0;
		while(par[x].first != x){
			OFF^=par[x].second;
			x=par[x].first;
		}
		return make_pair(x,OFF);
	}
	void merge(int x, int y){
		pi px=find(x);
		pi py=find(y);
		if(px.first == py.first){//same component
			if((px.second ^ py.second)== 0){ // not bipartite!
				rb.push_back({-1,bad,0,0});
				bad=1;
				return;
			} else{
				return;
			}
		}
		if(sz[px.first]<sz[py.first]){ // sz[x]>=sz[y]
			swap(px,py);
			swap(x,y);
		}
		rb.push_back({px.first,par[px.first].first,par[px.first].second,sz[px.first]});
		sz[px.first] += sz[py.first];
		rb.push_back({py.first,par[py.first].first,par[py.first].second,sz[py.first]});
		par[py.first].first = px.first;
		par[py.first].second = 1^px.second^py.second;
	}
	void rollback(int ss){
		while(rb.size() > ss){
			array<int,4>cur=rb.back();
			if(cur[0]==-1){
				bad=cur[1];
				rb.pop_back();
			} else{
				par[cur[0]].first=cur[1];
				par[cur[0]].second=cur[2];
				sz[cur[0]]=cur[3];
				rb.pop_back();
			}
			
		}
	}
}ufds;
void dnc(int s, int e, int optl, int optr){

	if(s>e)return;
	int mi=(s+e)/2;
	// use all of [1,mi]
	int sz1=ufds.rb.size();
	for(int i=s;i<=mi;i++){
		ufds.merge(E[i].first,E[i].second);
	}
	int sz2=ufds.rb.size();
	for(int i=optr;i>=optl;i--){
		ufds.merge(E[i].first,E[i].second);
		if(ufds.bad){
			ans[mi]=i;
			break;
		}
	}
	ufds.rollback(sz2);
	dnc(mi+1,e,ans[mi],optr);
	ufds.rollback(sz1);
	int rr=ufds.rb.size();
	for(int i=optr;i>=ans[mi];i--){
		ufds.merge(E[i].first,E[i].second);
	}
	dnc(s,mi-1,optl,ans[mi]);
	ufds.rollback(rr);
}

int32_t main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> q;

	for(int i=1;i<=m;i++){
		cin >> E[i].first >> E[i].second;
	}
	E[0].first=0;
	E[0].second=1;
	E[m+1].first=0;
	E[m+1].second=1;
	dnc(0,m,1,m+1); 
	while(q--){
		int l,r;cin>>l>>r;
		if(r<ans[l-1]){
			cout<<"YES\n";
		} else{
			cout<<"NO\n";
		}
	}
}	

Compilation message (stderr)

Joker.cpp: In member function 'void ufds_::rollback(long long int)':
Joker.cpp:63:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<long long int, 4> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   63 |   while(rb.size() > ss){
      |         ~~~~~~~~~~^~~~

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