Submission #957002

#	Time	Username	Problem	Language	Result	Execution time	Memory
957002		Rawlat_vanak	Joker (BOI20_joker)	C++17	100 / 100	343 ms	25532 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define speedIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define f first
#define s second

int poww(int a,int n){
	if(n==0) return 1;
	int b=poww(a,n/2);
	b=b*b;
	if(n%2==1) b*=a;
	return b;
}

struct changes{
	int u,v,sz,parity,idx;bool prev;
	changes(int _u,int _v,int _sz,int _parity,int _idx, bool _prev): u(_u), v(_v), sz(_sz),idx(_idx), parity(_parity), prev(_prev){}
};
	
vector<pair<int,int>> parent;
vector<pair<int,int>> edges;
vector<int> rk;
stack<changes> roll;
bool curr;
int n,m;

pair<int,int> find(int v){
	if(v==parent[v].f) return {parent[v].f,parent[v].s};
	pair<int,int> x=find(parent[v].f);
	return {x.f,x.s^parent[v].s};
}

void back(){
	if(roll.empty()) return;
	int u=roll.top().u;
	int v=roll.top().v;
	int sz=roll.top().sz;
	int parity=roll.top().parity;
	bool prev=roll.top().prev;
	roll.pop();
	parent[v].f=v;
	parent[v].s=parity;
	rk[u]=sz;
	curr=prev;
	return;
}

void merge(int e){
	int u=edges[e].f;int v=edges[e].s;
	auto x=find(u);
	auto y=find(v);
	u=x.f;v=y.f;
	int du=x.s;int dv=y.s;
	if(rk[u]<rk[v]) swap(u,v);
	bool prev=curr;
	int prprppr=parent[v].s;
	if(u==v){
		if(du^dv^1) curr=false;
	}else{
		parent[v].f=u;
		rk[u]+=rk[v];
		parent[v].s=du^dv^1;
	}
	roll.push({u,v,rk[u],prprppr,e,prev});
	return;
}

void rangeback(int l, int r){
	if(l>r) return;
	stack<changes> tmp;
	vector<bool> found(r-l+1,false);
	for(int i=l;i<=r;i++){
		if(roll.empty()) continue;
		if(found[i-l]) continue;
		while(roll.top().idx!=i){
			if(roll.top().idx<=r and roll.top().idx>=l){
				found[roll.top().idx-l]=true;
			}else{
				tmp.push(roll.top());
			}
			back();
		}
		found[i-l]=true;
		back();
	}
	while(!tmp.empty()){
		merge(tmp.top().idx);
		tmp.pop();
	}
}


vector<int> opt;
bool allbipar;

void calculate(int l,int r,int optl,int optr){
	if(l>r) return;
	int mid=(l+r)/2;
	for(int i=l;i<mid;i++) merge(i);//mid-1,optr+1

	for(int i=optr;i>=max(mid,optl);i--){
		if(curr==false) {opt[mid]=i;break;}
		merge(i);
	}
	if(opt[mid]==0) opt[mid]=mid-1;


	rangeback(opt[mid]+1,optr);
	merge(mid);
	calculate(mid+1,r,opt[mid],optr);

	rangeback(l,mid);
	for(int i=opt[mid]+1;i<=optr;i++) merge(i);
	calculate(l,mid-1,optl,opt[mid]);

	rangeback(opt[mid]+1,optr);
	return;

}

int32_t main(){
	speedIO;
	int t,q;
	//cin>>t;
	//t=1;
	///while(t--){
		cin>>n>>m>>q;
		parent.clear();parent.resize(n+5);
		rk.clear();rk.resize(n+5,1);
		opt.clear();opt.resize(m+5,0);
		edges.clear();edges.resize(m+5);
		curr=true;
		for(int i=0;i<n+5;i++){
			parent[i].f=i;parent[i].s=0;
		}
		for(int i=1;i<=m;i++){
			int a,b;
			cin>>a>>b;
			edges[i]={a,b};
		}
		edges[m+1]={n+1,n+2};edges[0]={n+3,n+4};
		allbipar=false;
		calculate(1,m,0,m+1);


		for(int i=0;i<q;i++){
			int l,r;
			cin>>l>>r;
			if(r<=opt[l]){
				cout<<"YES"<<'\n';
			}else{
				cout<<"NO"<<'\n';
			}
		}
		

		

	//}
	return 0;
}

Compilation message (stderr)

Joker.cpp: In constructor 'changes::changes(long long int, long long int, long long int, long long int, long long int, bool)':
Joker.cpp:18:20: warning: 'changes::idx' will be initialized after [-Wreorder]
   18 |  int u,v,sz,parity,idx;bool prev;
      |                    ^~~
Joker.cpp:18:13: warning:   'long long int changes::parity' [-Wreorder]
   18 |  int u,v,sz,parity,idx;bool prev;
      |             ^~~~~~
Joker.cpp:19:2: warning:   when initialized here [-Wreorder]
   19 |  changes(int _u,int _v,int _sz,int _parity,int _idx, bool _prev): u(_u), v(_v), sz(_sz),idx(_idx), parity(_parity), prev(_prev){}
      |  ^~~~~~~
Joker.cpp: In function 'int32_t main()':
Joker.cpp:125:6: warning: unused variable 't' [-Wunused-variable]
  125 |  int t,q;
      |      ^

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