oj.uz

Submission #907392

# Submission time Handle Problem Language Result Execution time Memory
907392 2024-01-15T13:21:04 Z sunwukong123 Joker (BOI20_joker) C++14
25 / 100
 215 ms 30976 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];
	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";
		}
	}
}

Compilation message

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.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 3 ms 6748 KB Output is correct
4 Incorrect 2 ms 6572 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 3 ms 6744 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 109 ms 21792 KB Output is correct
4 Correct 215 ms 30976 KB Output is correct
5 Correct 167 ms 29888 KB Output is correct
6 Correct 148 ms 21480 KB Output is correct
7 Correct 189 ms 20840 KB Output is correct
8 Correct 170 ms 17684 KB Output is correct
9 Correct 177 ms 21956 KB Output is correct
10 Correct 206 ms 29692 KB Output is correct
11 Correct 160 ms 22216 KB Output is correct
12 Correct 163 ms 29792 KB Output is correct
13 Correct 168 ms 15568 KB Output is correct
14 Correct 175 ms 18108 KB Output is correct
15 Correct 202 ms 30276 KB Output is correct
16 Correct 206 ms 30400 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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