Submission #962029

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
962029	2024-04-13T05:12:50 Z	pcc	Joker (BOI20_joker)	C++17	25 / 100	86 ms	26868 KB

Joker

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

const int mxn = 4e5+30;
int N,M,Q;

struct DSU{
	vector<pii> sop,dop;
	vector<int> cop;
	bool cyc;
	int dsu[mxn],sz[mxn];
	void init(int n){
		cyc = false;
		for(int i = 0;i<=n;i++)dsu[i] = i,sz[i] = 1;
	}
	int root(int k){
		return k == dsu[k]?k:root(dsu[k]);
	}
	void onion(int a,int b){
		 a = root(a),b = root(b);
		 if(a == b){
			 sop.push_back(pii(0,0));
			 dop.push_back(pii(0,0));
			 return;
		 }
		 if(sz[a]<sz[b])swap(a,b);
		 sop.push_back(pii(a,sz[a]));
		 dop.push_back(pii(b,b));
		 dsu[b] = a;
		 sz[a] += sz[b];
		 return;
	}
	void roll(){
		for(int i = 0;i<2;i++){
		{
			auto [a,b] = sop.back();sop.pop_back();
			sz[a] = b;
		}{
			auto [a,b] = dop.back();dop.pop_back();
			dsu[a] = b;
		}{
			auto a = cop.back();cop.pop_back();
			cyc = a;
		}}
		return;
	}
	void add_edge(int a,int b){
		onion(a,b+N);
		onion(b,a+N);
		cop.push_back(cyc);
		if(root(a) == root(a+N))cyc = true;
		cop.push_back(cyc);
		if(root(b) == root(b+N))cyc = true;
		assert(cop.size() == dop.size());
		return;
	}
};

DSU dsu;
pii edges[mxn];
pii req[mxn];
int rp[mxn];

void dc(int l,int r,int sl,int sr){
	//cerr<<l<<' '<<r<<':'<<sl<<' '<<sr<<endl;
	if(l == r){
		for(int i = sl;i<=sr;i++){
			rp[i] = l;
		}
		return;
	}
	int mid = (l+r)>>1;
	bool f = false;
	for(int i = r;i>mid;i--){
		auto [a,b] = edges[i];
		dsu.add_edge(a,b);
	}
	//cerr<<l<<' '<<mid<<' '<<r<<":"<<sl<<' '<<sr<<','<<dsu.cyc<<endl;
	//for(int i = 1;i<=N;i++)cerr<<dsu.root(i)<<' ';cerr<<endl;
	if(dsu.cyc){
		for(int i = r;i>mid;i--){
			dsu.roll();
		}
		dc(mid+1,r,sl,sr);
		return;
	}
	int opt = sl;
	for(int i = sl;i<=sr;i++){
		auto [a,b] = edges[i];
		dsu.add_edge(a,b);
		opt = i;
		if(dsu.cyc)break;
	}
	for(int i = sl;i<=opt;i++){
		dsu.roll();
	}
	if(sl != opt)dc(l,mid,sl,opt-1);
	for(int i = r;i>mid;i--){
		dsu.roll();
	}
	for(int i = sl;i<opt;i++){
		auto [a,b] = edges[i];
		dsu.add_edge(a,b);
	}
	dc(mid+1,r,opt,sr);
	for(int i = sl;i<opt;i++){
		dsu.roll();
	}
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M>>Q;
	N += 2;
	for(int i = 1;i<=M;i++)cin>>edges[i].fs>>edges[i].sc;
	for(int i = 1;i<=Q;i++)cin>>req[i].fs>>req[i].sc;
	edges[M+2] = edges[0] = edges[M+1] = pii(N+1,N+2);
	dsu.init(N*2+10);

	{
		for(int i = M;i>=1;i--){
			dsu.add_edge(edges[i].fs,edges[i].sc);
			if(dsu.cyc)rp[i] = 1;
		}
		for(int i = 1;i<=Q;i++){
			int r = req[i].sc;
			if(rp[r+1])cout<<"YES\n";
			else cout<<"NO\n";
		}
		return 0;
	}

	dc(0,M+1,0,M);
	//for(int i = 0;i<=M;i++)cerr<<rp[i]<<' ';cerr<<endl;
	for(int i = 1;i<=Q;i++){
		auto [s,e] = req[i];
		if(rp[s-1]>=e+1)cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}

Compilation message

Joker.cpp: In function 'void dc(int, int, int, int)':
Joker.cpp:82:7: warning: unused variable 'f' [-Wunused-variable]
   82 |  bool f = false;
      |       ^

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	8536 KB	Output is correct
2	Correct	2 ms	8540 KB	Output is correct
3	Correct	68 ms	21352 KB	Output is correct
4	Correct	64 ms	21612 KB	Output is correct
5	Correct	74 ms	25952 KB	Output is correct
6	Correct	71 ms	26868 KB	Output is correct
7	Correct	86 ms	25560 KB	Output is correct
8	Correct	65 ms	24680 KB	Output is correct
9	Correct	73 ms	24708 KB	Output is correct
10	Correct	76 ms	25564 KB	Output is correct
11	Correct	71 ms	25328 KB	Output is correct
12	Correct	67 ms	26824 KB	Output is correct
13	Correct	67 ms	25064 KB	Output is correct
14	Correct	70 ms	25240 KB	Output is correct
15	Correct	70 ms	26148 KB	Output is correct
16	Correct	72 ms	26092 KB	Output is correct