Submission #255987

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
255987	2020-08-02T07:33:24 Z	임성재(#5031)	Joker (BOI20_joker)	C++17	41 / 100	1576 ms	4840 KB

Joker

#include<bits/stdc++.h>  
using namespace std;  
  
#define fast ios::sync_with_stdio(false);cin.tie(NULL)  
#define fi first  
#define se second  
#define all(v) (v).begin(),(v).end()  
#define pb push_back  
#define eb emplace_back
#define pre(a) cout<<fixed; cout.precision(a)
#define mp make_pair
  
typedef long long ll;  
typedef pair<int,int> pii;  
typedef pair<ll,ll> pll;  
const long long INF = 1e18;
const int inf = 1e9;

int n, m, q;
int l, r;
vector<pii> e;
int p[200010];
int rk[200010];
bool val[200010];
bool pval[200010];
int ans[200010];

int Find(int a) {
	if(p[a] == a) return a;

	int ret = Find(p[a]);
	val[a] = val[p[a]] ^ pval[a];
	
	return ret;
}

void Union(int i, int j) {
	int a = Find(i);
	int b = Find(j);

	if(rk[a] < rk[b]) p[a] = b, pval[a] = 1 ^ val[i] ^ val[j];
	else if(rk[b] < rk[a]) p[b] = a, pval[b] = 1 ^ val[i] ^ val[j];
	else p[b] = a, rk[a]++, pval[b] = 1 ^ val[i] ^ val[j];
}

int main() {
	fast;

	cin >> n >> m >> q;


	for(int i=1; i<=m; i++) {
		int u, v;

		cin >> u >> v;

		e.eb(u, v);
	}

	reverse(all(e));

	for(int l=1; l<=min(200, m); l++) {
		for(int i=1; i<=n; i++) p[i] = i, pval[i] = 0, val[i] = 0, rk[i] = 0;

		for(int k = m - l + 1; k<m; k++) {
			auto i = e[k];
			if(Find(i.fi) == Find(i.se)) {
				if((val[i.fi] ^ val[i.se]) == 0) {
					ans[l] = m+1;
				}
				continue;
			}

			Union(i.fi, i.se);
		}

		if(ans[l]) continue;

		for(int k=0; k<m; k++) {
			auto i = e[k];
			if(Find(i.fi) == Find(i.se)) {
				if((val[i.fi] ^ val[i.se]) == 0) {
					ans[l] = m - k;
					break;
				}
				else continue;
			}

			Union(i.fi, i.se);
		}
	}

	while(q--) {
		cin >> l >> r;

		if(r < ans[l]) cout << "YES\n";
		else cout << "NO\n";
	}
	
}

Subtask #1
6.0 / 6.0

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

Subtask #2
0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	1 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	1 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	1 ms	384 KB	Output is correct
20	Correct	1 ms	384 KB	Output is correct
21	Correct	1 ms	384 KB	Output is correct
22	Correct	1 ms	384 KB	Output is correct
23	Correct	1 ms	384 KB	Output is correct
24	Correct	1 ms	384 KB	Output is correct
25	Correct	1 ms	384 KB	Output is correct
26	Correct	1 ms	384 KB	Output is correct
27	Correct	1 ms	384 KB	Output is correct
28	Correct	1 ms	384 KB	Output is correct
29	Correct	9 ms	384 KB	Output is correct
30	Incorrect	6 ms	384 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	688 ms	3692 KB	Output is correct
4	Correct	1576 ms	4584 KB	Output is correct
5	Correct	210 ms	4460 KB	Output is correct
6	Correct	205 ms	3688 KB	Output is correct
7	Correct	216 ms	3688 KB	Output is correct
8	Correct	445 ms	3432 KB	Output is correct
9	Correct	457 ms	3816 KB	Output is correct
10	Correct	796 ms	4716 KB	Output is correct
11	Correct	865 ms	3728 KB	Output is correct
12	Correct	699 ms	4584 KB	Output is correct
13	Correct	1006 ms	3048 KB	Output is correct
14	Correct	458 ms	3432 KB	Output is correct
15	Correct	719 ms	4244 KB	Output is correct
16	Correct	802 ms	4712 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	1 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	1 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	1 ms	384 KB	Output is correct
20	Correct	1 ms	384 KB	Output is correct
21	Correct	1 ms	384 KB	Output is correct
22	Correct	1 ms	384 KB	Output is correct
23	Correct	1 ms	384 KB	Output is correct
24	Correct	1 ms	384 KB	Output is correct
25	Correct	1 ms	384 KB	Output is correct
26	Correct	1 ms	384 KB	Output is correct
27	Correct	1 ms	384 KB	Output is correct
28	Correct	1 ms	384 KB	Output is correct
29	Correct	688 ms	3692 KB	Output is correct
30	Correct	1576 ms	4584 KB	Output is correct
31	Correct	210 ms	4460 KB	Output is correct
32	Correct	205 ms	3688 KB	Output is correct
33	Correct	216 ms	3688 KB	Output is correct
34	Correct	445 ms	3432 KB	Output is correct
35	Correct	457 ms	3816 KB	Output is correct
36	Correct	796 ms	4716 KB	Output is correct
37	Correct	865 ms	3728 KB	Output is correct
38	Correct	699 ms	4584 KB	Output is correct
39	Correct	1006 ms	3048 KB	Output is correct
40	Correct	458 ms	3432 KB	Output is correct
41	Correct	719 ms	4244 KB	Output is correct
42	Correct	802 ms	4712 KB	Output is correct
43	Correct	666 ms	3816 KB	Output is correct
44	Correct	1571 ms	4560 KB	Output is correct
45	Correct	1497 ms	4588 KB	Output is correct
46	Correct	180 ms	3680 KB	Output is correct
47	Correct	182 ms	3688 KB	Output is correct
48	Correct	542 ms	3904 KB	Output is correct
49	Correct	886 ms	4816 KB	Output is correct
50	Correct	959 ms	3432 KB	Output is correct
51	Correct	809 ms	4200 KB	Output is correct
52	Correct	694 ms	4712 KB	Output is correct
53	Correct	748 ms	3048 KB	Output is correct
54	Correct	536 ms	3560 KB	Output is correct
55	Correct	741 ms	4076 KB	Output is correct
56	Correct	876 ms	4840 KB	Output is correct

Subtask #5
0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	1 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	1 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	1 ms	384 KB	Output is correct
20	Correct	1 ms	384 KB	Output is correct
21	Correct	1 ms	384 KB	Output is correct
22	Correct	1 ms	384 KB	Output is correct
23	Correct	1 ms	384 KB	Output is correct
24	Correct	1 ms	384 KB	Output is correct
25	Correct	1 ms	384 KB	Output is correct
26	Correct	1 ms	384 KB	Output is correct
27	Correct	1 ms	384 KB	Output is correct
28	Correct	1 ms	384 KB	Output is correct
29	Correct	9 ms	384 KB	Output is correct
30	Incorrect	6 ms	384 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

Subtask #6
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	1 ms	384 KB	Output is correct
16	Correct	1 ms	384 KB	Output is correct
17	Correct	1 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	1 ms	384 KB	Output is correct
20	Correct	1 ms	384 KB	Output is correct
21	Correct	1 ms	384 KB	Output is correct
22	Correct	1 ms	384 KB	Output is correct
23	Correct	1 ms	384 KB	Output is correct
24	Correct	1 ms	384 KB	Output is correct
25	Correct	1 ms	384 KB	Output is correct
26	Correct	1 ms	384 KB	Output is correct
27	Correct	1 ms	384 KB	Output is correct
28	Correct	1 ms	384 KB	Output is correct
29	Correct	9 ms	384 KB	Output is correct
30	Incorrect	6 ms	384 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

Submission #255987

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 0 / 8.0

Subtask #3 25.0 / 25.0

Subtask #4 10.0 / 10.0

Subtask #5 0 / 22.0

Subtask #6 0 / 29.0

Subtask #1
6.0 / 6.0

Subtask #2
0 / 8.0

Subtask #3
25.0 / 25.0

Subtask #4
10.0 / 10.0

Subtask #5
0 / 22.0

Subtask #6
0 / 29.0