oj.uz

Submission #907401

# Submission time Handle Problem Language Result Execution time Memory
907401 2024-01-15T13:32:22 Z sunwukong123 Joker (BOI20_joker) C++14
25 / 100
 213 ms 27844 KB 
#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;
	// block all of [s,mi-1]
	int sz1=ufds.rb.size();
	bool done=0;
	for(int i=s;i<=mi-1;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[m+1].first=0;
	E[m+1].second=1;
	dnc(1,m,1,m+1); 
	while(q--){
		int l,r;cin>>l>>r;
		if(r<ans[l]){
			cout<<"YES\n";
		} else{
			cout<<"NO\n";
		}
	}
}

Compilation message

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){
      |         ~~~~~~~~~~^~~~
Joker.cpp: In function 'void dnc(long long int, long long int, long long int, long long int)':
Joker.cpp:84:7: warning: unused variable 'done' [-Wunused-variable]
   84 |  bool done=0;
      |       ^~~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 137 ms 26620 KB Output is correct
4 Correct 164 ms 27644 KB Output is correct
5 Correct 122 ms 27844 KB Output is correct
6 Correct 133 ms 19396 KB Output is correct
7 Correct 129 ms 19920 KB Output is correct
8 Correct 147 ms 18116 KB Output is correct
9 Correct 167 ms 18196 KB Output is correct
10 Correct 207 ms 27672 KB Output is correct
11 Correct 152 ms 18676 KB Output is correct
12 Correct 201 ms 26304 KB Output is correct
13 Correct 145 ms 15112 KB Output is correct
14 Correct 157 ms 18640 KB Output is correct
15 Correct 199 ms 27588 KB Output is correct
16 Correct 213 ms 27844 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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