oj.uz

Submission #962043

# Submission time Handle Problem Language Result Execution time Memory
962043 2024-04-13T05:39:17 Z pcc Joker (BOI20_joker) C++17
14 / 100
 2000 ms 27212 KB 
#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 ans[2020][2020];

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M>>Q;
	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);
	N += 2;
	dsu.init(N*2+10);

	for(int i = 0;i<=M;i++){
		dsu.add_edge(edges[i].fs,edges[i].sc);
		for(int j = M+1;j>i;j--){
			dsu.add_edge(edges[j].fs,edges[j].sc);
			ans[i][j] = dsu.cyc;
			//cerr<<i<<' '<<j<<":";
			//for(int k = 0;k<=N;k++)cerr<<dsu.root(k)<<' ';cerr<<endl;
		}
		for(int j = M+1;j>i;j--)dsu.roll();
	}
	for(int i = 1;i<=Q;i++){
		auto [a,b] = req[i];
		if(ans[a-1][b+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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 2 ms 10708 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10844 KB Output is correct
19 Correct 3 ms 10844 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 2 ms 10844 KB Output is correct
22 Correct 2 ms 10716 KB Output is correct
23 Correct 3 ms 10844 KB Output is correct
24 Correct 2 ms 10844 KB Output is correct
25 Correct 2 ms 10844 KB Output is correct
26 Correct 3 ms 10848 KB Output is correct
27 Correct 3 ms 10848 KB Output is correct
28 Correct 2 ms 10848 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 2 ms 10708 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10844 KB Output is correct
19 Correct 3 ms 10844 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 2 ms 10844 KB Output is correct
22 Correct 2 ms 10716 KB Output is correct
23 Correct 3 ms 10844 KB Output is correct
24 Correct 2 ms 10844 KB Output is correct
25 Correct 2 ms 10844 KB Output is correct
26 Correct 3 ms 10848 KB Output is correct
27 Correct 3 ms 10848 KB Output is correct
28 Correct 2 ms 10848 KB Output is correct
29 Correct 13 ms 17120 KB Output is correct
30 Correct 50 ms 23348 KB Output is correct
31 Correct 80 ms 25392 KB Output is correct
32 Correct 76 ms 25388 KB Output is correct
33 Correct 78 ms 25168 KB Output is correct
34 Correct 64 ms 25368 KB Output is correct
35 Correct 68 ms 25384 KB Output is correct
36 Correct 45 ms 25172 KB Output is correct
37 Correct 47 ms 25168 KB Output is correct
38 Correct 43 ms 25384 KB Output is correct
39 Correct 47 ms 25396 KB Output is correct
40 Correct 60 ms 25172 KB Output is correct
41 Correct 66 ms 25384 KB Output is correct
42 Correct 57 ms 25168 KB Output is correct
43 Correct 93 ms 25392 KB Output is correct
44 Correct 85 ms 25168 KB Output is correct
45 Correct 70 ms 25372 KB Output is correct
46 Correct 64 ms 25168 KB Output is correct
47 Correct 59 ms 25168 KB Output is correct
48 Correct 63 ms 25388 KB Output is correct
49 Correct 60 ms 25168 KB Output is correct
50 Correct 63 ms 25168 KB Output is correct
51 Correct 91 ms 25380 KB Output is correct
52 Correct 85 ms 25384 KB Output is correct
53 Correct 75 ms 25172 KB Output is correct
54 Correct 72 ms 25388 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Execution timed out 2063 ms 24880 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 2 ms 10708 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10844 KB Output is correct
19 Correct 3 ms 10844 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 2 ms 10844 KB Output is correct
22 Correct 2 ms 10716 KB Output is correct
23 Correct 3 ms 10844 KB Output is correct
24 Correct 2 ms 10844 KB Output is correct
25 Correct 2 ms 10844 KB Output is correct
26 Correct 3 ms 10848 KB Output is correct
27 Correct 3 ms 10848 KB Output is correct
28 Correct 2 ms 10848 KB Output is correct
29 Execution timed out 2063 ms 24880 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 2 ms 10708 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10844 KB Output is correct
19 Correct 3 ms 10844 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 2 ms 10844 KB Output is correct
22 Correct 2 ms 10716 KB Output is correct
23 Correct 3 ms 10844 KB Output is correct
24 Correct 2 ms 10844 KB Output is correct
25 Correct 2 ms 10844 KB Output is correct
26 Correct 3 ms 10848 KB Output is correct
27 Correct 3 ms 10848 KB Output is correct
28 Correct 2 ms 10848 KB Output is correct
29 Correct 13 ms 17120 KB Output is correct
30 Correct 50 ms 23348 KB Output is correct
31 Correct 80 ms 25392 KB Output is correct
32 Correct 76 ms 25388 KB Output is correct
33 Correct 78 ms 25168 KB Output is correct
34 Correct 64 ms 25368 KB Output is correct
35 Correct 68 ms 25384 KB Output is correct
36 Correct 45 ms 25172 KB Output is correct
37 Correct 47 ms 25168 KB Output is correct
38 Correct 43 ms 25384 KB Output is correct
39 Correct 47 ms 25396 KB Output is correct
40 Correct 60 ms 25172 KB Output is correct
41 Correct 66 ms 25384 KB Output is correct
42 Correct 57 ms 25168 KB Output is correct
43 Correct 93 ms 25392 KB Output is correct
44 Correct 85 ms 25168 KB Output is correct
45 Correct 70 ms 25372 KB Output is correct
46 Correct 64 ms 25168 KB Output is correct
47 Correct 59 ms 25168 KB Output is correct
48 Correct 63 ms 25388 KB Output is correct
49 Correct 60 ms 25168 KB Output is correct
50 Correct 63 ms 25168 KB Output is correct
51 Correct 91 ms 25380 KB Output is correct
52 Correct 85 ms 25384 KB Output is correct
53 Correct 75 ms 25172 KB Output is correct
54 Correct 72 ms 25388 KB Output is correct
55 Execution timed out 2055 ms 27212 KB Time limit exceeded
56 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 2 ms 10844 KB Output is correct
11 Correct 2 ms 10840 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 2 ms 10844 KB Output is correct
14 Correct 2 ms 10708 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10844 KB Output is correct
19 Correct 3 ms 10844 KB Output is correct
20 Correct 2 ms 10844 KB Output is correct
21 Correct 2 ms 10844 KB Output is correct
22 Correct 2 ms 10716 KB Output is correct
23 Correct 3 ms 10844 KB Output is correct
24 Correct 2 ms 10844 KB Output is correct
25 Correct 2 ms 10844 KB Output is correct
26 Correct 3 ms 10848 KB Output is correct
27 Correct 3 ms 10848 KB Output is correct
28 Correct 2 ms 10848 KB Output is correct
29 Correct 13 ms 17120 KB Output is correct
30 Correct 50 ms 23348 KB Output is correct
31 Correct 80 ms 25392 KB Output is correct
32 Correct 76 ms 25388 KB Output is correct
33 Correct 78 ms 25168 KB Output is correct
34 Correct 64 ms 25368 KB Output is correct
35 Correct 68 ms 25384 KB Output is correct
36 Correct 45 ms 25172 KB Output is correct
37 Correct 47 ms 25168 KB Output is correct
38 Correct 43 ms 25384 KB Output is correct
39 Correct 47 ms 25396 KB Output is correct
40 Correct 60 ms 25172 KB Output is correct
41 Correct 66 ms 25384 KB Output is correct
42 Correct 57 ms 25168 KB Output is correct
43 Correct 93 ms 25392 KB Output is correct
44 Correct 85 ms 25168 KB Output is correct
45 Correct 70 ms 25372 KB Output is correct
46 Correct 64 ms 25168 KB Output is correct
47 Correct 59 ms 25168 KB Output is correct
48 Correct 63 ms 25388 KB Output is correct
49 Correct 60 ms 25168 KB Output is correct
50 Correct 63 ms 25168 KB Output is correct
51 Correct 91 ms 25380 KB Output is correct
52 Correct 85 ms 25384 KB Output is correct
53 Correct 75 ms 25172 KB Output is correct
54 Correct 72 ms 25388 KB Output is correct
55 Execution timed out 2063 ms 24880 KB Time limit exceeded
56 Halted 0 ms 0 KB -