제출 #907392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
907392		sunwukong123	Joker (BOI20_joker)	C++14	25 / 100	215 ms	30976 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];
	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);
	}
	int 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!
				return 1;
			} else{
				return 0;
			}
		}
		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;
		return 0;
	}
	void rollback(int ss){
		while(rb.size() > ss){
			array<int,4>cur=rb.back();
			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;
	debug(s,e,optl,optr);
	// block all of [s,mi-1]
	int sz1=ufds.rb.size();
	bool done=0;
	for(int i=s;i<=mi-1;i++){
		int res=ufds.merge(E[i].first,E[i].second);
		if(res){
			done=1;
		}
	}
	if(done){
		for(int i=mi;i<=e;i++){
			ans[i]=m+1;
		}
		ufds.rollback(sz1);
		for(int i=optr;i>=optl;i--){
			ufds.merge(E[i].first,E[i].second);
		}
		dnc(s,mi-1,optl,optr);
		ufds.rollback(sz1);
		return;
	}
	int sz2=ufds.rb.size();
	for(int i=min(optr,m);i>=optl;i--){
		int res=ufds.merge(E[i].first,E[i].second);
		if(res){
			ans[mi]=i;
			break;
		}
	}
	ufds.rollback(sz2);
	dnc(mi+1,e,ans[mi],optr);
	ufds.rollback(sz1);
	for(int i=optr;i>=optl;i--){
		ufds.merge(E[i].first,E[i].second);
	}
	dnc(s,mi-1,optl,ans[mi]);
	ufds.rollback(sz1);
}

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;
	}
	dnc(1,m,1,m+1); 
	for(int i=1;i<=m;i++){
		debug(i,ans[i]);
	}
	while(q--){
		int l,r;cin>>l>>r;
		if(r+1<=ans[l]){
			cout<<"YES\n";
		} else{
			cout<<"NO\n";
		}
	}
}	

컴파일 시 표준 에러 (stderr) 메시지

Joker.cpp: In member function 'void ufds_::rollback(long long int)':
Joker.cpp:61: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]
   61 |   while(rb.size() > ss){
      |         ~~~~~~~~~~^~~~

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