oj.uz

답안 #907400

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
907400 2024-01-15T13:31:19 Z sunwukong123 Joker (BOI20_joker) C++14
25 / 100
 231 ms 28352 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;
	}
	dnc(1,m,1,m); 
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6748 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6748 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 147 ms 27936 KB Output is correct
4 Correct 211 ms 28004 KB Output is correct
5 Correct 140 ms 27000 KB Output is correct
6 Correct 135 ms 18372 KB Output is correct
7 Correct 141 ms 19428 KB Output is correct
8 Correct 176 ms 19976 KB Output is correct
9 Correct 174 ms 19004 KB Output is correct
10 Correct 224 ms 26872 KB Output is correct
11 Correct 181 ms 19700 KB Output is correct
12 Correct 177 ms 26348 KB Output is correct
13 Correct 147 ms 14032 KB Output is correct
14 Correct 157 ms 18580 KB Output is correct
15 Correct 205 ms 27980 KB Output is correct
16 Correct 231 ms 28352 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6748 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6748 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6748 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 -