oj.uz

Submission #956978

# Submission time Handle Problem Language Result Execution time Memory
956978 2024-04-02T18:36:07 Z Rawlat_vanak Joker (BOI20_joker) C++17
25 / 100
 243 ms 24464 KB 
#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(allbipar==true) return;
	if(l>r) return;
	int mid=(l+r)/2;
	for(int i=l;i<mid;i++) merge(i);

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

	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

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:126:6: warning: unused variable 't' [-Wunused-variable]
  126 |  int t,q;
      |      ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 372 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 372 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 183 ms 21972 KB Output is correct
4 Correct 74 ms 23888 KB Output is correct
5 Correct 137 ms 23980 KB Output is correct
6 Correct 163 ms 21972 KB Output is correct
7 Correct 183 ms 22076 KB Output is correct
8 Correct 204 ms 20452 KB Output is correct
9 Correct 199 ms 21360 KB Output is correct
10 Correct 239 ms 24036 KB Output is correct
11 Correct 204 ms 21712 KB Output is correct
12 Correct 215 ms 24176 KB Output is correct
13 Correct 204 ms 19964 KB Output is correct
14 Correct 198 ms 20960 KB Output is correct
15 Correct 242 ms 22780 KB Output is correct
16 Correct 243 ms 24464 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 372 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 372 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 372 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -