답안 #1115866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1115866	2024-11-21T02:55:54 Z	vjudge1	Political Development (BOI17_politicaldevelopment)	C++17	100 / 100	327 ms	321268 KB

politicaldevelopment

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,popcnt,lzcnt")
#include <bits/stdc++.h>
using namespace std;

bitset<50001> G[50001], cur;
vector<vector<int>> C[2];

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, k, sz, u, v; cin >> n >> k;
	for (int i = 0; i < n; ++i) C[1].push_back({i});
	for (u = 0; u < n; ++u) {
		cin >> sz;
		while (sz--) cin >> v, G[min(u, v)][max(u, v)] = 1;
	}
	vector<int> tmp; int _c, _p;
	for (sz = 2; sz <= k; ++sz) {
		_c = sz & 1; _p = 1 ^ _c; C[_c].clear();
		for (auto small_clique : C[_p]) {
			cur = G[small_clique[0]];
			for (int i = 1; i + 1 < sz; ++i) cur &= G[small_clique[i]];
			for (int j = cur._Find_first(); j < n; j = cur._Find_next(j)) if (cur[j]) {
				tmp = small_clique; tmp.push_back(j);
				C[_c].push_back(tmp);
			}
		}
		if (C[_c].empty()) {cout << sz - 1; return 0;}
		// cout << sz << "!!" << '\n';
		// for (auto clique : C[sz]) {
			// for (int i : clique) cout << i << ' ';
			// cout << '\n';
		// }
	}
	cout << k;
}

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	7 ms	31824 KB	Output is correct
4	Correct	5 ms	11344 KB	Output is correct
5	Correct	5 ms	13568 KB	Output is correct
6	Correct	10 ms	31824 KB	Output is correct
7	Correct	7 ms	31824 KB	Output is correct
8	Correct	3 ms	848 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	3 ms	2896 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	7 ms	31824 KB	Output is correct
4	Correct	5 ms	11344 KB	Output is correct
5	Correct	5 ms	13568 KB	Output is correct
6	Correct	10 ms	31824 KB	Output is correct
7	Correct	7 ms	31824 KB	Output is correct
8	Correct	3 ms	848 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	3 ms	2896 KB	Output is correct
11	Correct	5 ms	9296 KB	Output is correct
12	Correct	7 ms	11344 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	7 ms	19708 KB	Output is correct
15	Correct	1 ms	336 KB	Output is correct
16	Correct	10 ms	31824 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct
18	Correct	9 ms	31824 KB	Output is correct
19	Correct	4 ms	848 KB	Output is correct
20	Correct	8 ms	31568 KB	Output is correct
21	Correct	10 ms	31568 KB	Output is correct
22	Correct	4 ms	2896 KB	Output is correct
23	Correct	12 ms	31836 KB	Output is correct
24	Correct	3 ms	2896 KB	Output is correct
25	Correct	11 ms	31836 KB	Output is correct
26	Correct	11 ms	32036 KB	Output is correct
27	Correct	10 ms	31824 KB	Output is correct
28	Correct	12 ms	31824 KB	Output is correct
29	Correct	11 ms	31824 KB	Output is correct
30	Correct	14 ms	31824 KB	Output is correct
31	Correct	12 ms	31824 KB	Output is correct
32	Correct	12 ms	31824 KB	Output is correct
33	Correct	11 ms	32036 KB	Output is correct
34	Correct	12 ms	31824 KB	Output is correct
35	Correct	6 ms	17232 KB	Output is correct
36	Correct	6 ms	17232 KB	Output is correct
37	Correct	6 ms	17232 KB	Output is correct
38	Correct	4 ms	8784 KB	Output is correct
39	Correct	4 ms	8784 KB	Output is correct
40	Correct	15 ms	32140 KB	Output is correct
41	Correct	4 ms	8784 KB	Output is correct
42	Correct	18 ms	32276 KB	Output is correct
43	Correct	15 ms	32140 KB	Output is correct

Subtask #3
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	844 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	297 ms	296696 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	303 ms	297972 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Correct	288 ms	297972 KB	Output is correct
16	Correct	290 ms	319228 KB	Output is correct
17	Correct	276 ms	321268 KB	Output is correct
18	Correct	295 ms	315544 KB	Output is correct

Subtask #4
38.0 / 38.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	7 ms	31824 KB	Output is correct
4	Correct	5 ms	11344 KB	Output is correct
5	Correct	5 ms	13568 KB	Output is correct
6	Correct	10 ms	31824 KB	Output is correct
7	Correct	7 ms	31824 KB	Output is correct
8	Correct	3 ms	848 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	3 ms	2896 KB	Output is correct
11	Correct	5 ms	9296 KB	Output is correct
12	Correct	7 ms	11344 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	7 ms	19708 KB	Output is correct
15	Correct	1 ms	336 KB	Output is correct
16	Correct	10 ms	31824 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct
18	Correct	9 ms	31824 KB	Output is correct
19	Correct	4 ms	848 KB	Output is correct
20	Correct	8 ms	31568 KB	Output is correct
21	Correct	10 ms	31568 KB	Output is correct
22	Correct	4 ms	2896 KB	Output is correct
23	Correct	12 ms	31836 KB	Output is correct
24	Correct	3 ms	2896 KB	Output is correct
25	Correct	11 ms	31836 KB	Output is correct
26	Correct	11 ms	32036 KB	Output is correct
27	Correct	10 ms	31824 KB	Output is correct
28	Correct	12 ms	31824 KB	Output is correct
29	Correct	11 ms	31824 KB	Output is correct
30	Correct	14 ms	31824 KB	Output is correct
31	Correct	12 ms	31824 KB	Output is correct
32	Correct	12 ms	31824 KB	Output is correct
33	Correct	11 ms	32036 KB	Output is correct
34	Correct	12 ms	31824 KB	Output is correct
35	Correct	6 ms	17232 KB	Output is correct
36	Correct	6 ms	17232 KB	Output is correct
37	Correct	6 ms	17232 KB	Output is correct
38	Correct	4 ms	8784 KB	Output is correct
39	Correct	4 ms	8784 KB	Output is correct
40	Correct	15 ms	32140 KB	Output is correct
41	Correct	4 ms	8784 KB	Output is correct
42	Correct	18 ms	32276 KB	Output is correct
43	Correct	15 ms	32140 KB	Output is correct
44	Correct	327 ms	41008 KB	Output is correct
45	Correct	1 ms	336 KB	Output is correct
46	Correct	14 ms	32184 KB	Output is correct
47	Correct	22 ms	32908 KB	Output is correct
48	Correct	17 ms	32140 KB	Output is correct
49	Correct	24 ms	33080 KB	Output is correct
50	Correct	23 ms	32908 KB	Output is correct
51	Correct	39 ms	34232 KB	Output is correct
52	Correct	5 ms	3152 KB	Output is correct
53	Correct	37 ms	34212 KB	Output is correct
54	Correct	48 ms	34056 KB	Output is correct
55	Correct	14 ms	31824 KB	Output is correct
56	Correct	4 ms	3152 KB	Output is correct
57	Correct	3 ms	840 KB	Output is correct
58	Correct	38 ms	29960 KB	Output is correct
59	Correct	28 ms	32468 KB	Output is correct
60	Correct	12 ms	31824 KB	Output is correct
61	Correct	31 ms	32472 KB	Output is correct
62	Correct	30 ms	32456 KB	Output is correct
63	Correct	313 ms	41008 KB	Output is correct
64	Correct	171 ms	35640 KB	Output is correct
65	Correct	14 ms	32080 KB	Output is correct
66	Correct	32 ms	32456 KB	Output is correct
67	Correct	92 ms	33852 KB	Output is correct
68	Correct	162 ms	35680 KB	Output is correct
69	Correct	14 ms	32080 KB	Output is correct
70	Correct	29 ms	32908 KB	Output is correct
71	Correct	92 ms	33608 KB	Output is correct
72	Correct	56 ms	33304 KB	Output is correct
73	Correct	10 ms	31824 KB	Output is correct
74	Correct	26 ms	33080 KB	Output is correct
75	Correct	55 ms	33280 KB	Output is correct
76	Correct	16 ms	32140 KB	Output is correct
77	Correct	25 ms	33032 KB	Output is correct
78	Correct	10 ms	31824 KB	Output is correct
79	Correct	13 ms	17804 KB	Output is correct
80	Correct	17 ms	32324 KB	Output is correct
81	Correct	26 ms	33200 KB	Output is correct
82	Correct	4 ms	8784 KB	Output is correct
83	Correct	12 ms	17804 KB	Output is correct
84	Correct	22 ms	32908 KB	Output is correct
85	Correct	4 ms	9040 KB	Output is correct
86	Correct	22 ms	32908 KB	Output is correct

Subtask #5
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	7 ms	31824 KB	Output is correct
4	Correct	5 ms	11344 KB	Output is correct
5	Correct	5 ms	13568 KB	Output is correct
6	Correct	10 ms	31824 KB	Output is correct
7	Correct	7 ms	31824 KB	Output is correct
8	Correct	3 ms	848 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	3 ms	2896 KB	Output is correct
11	Correct	5 ms	9296 KB	Output is correct
12	Correct	7 ms	11344 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	7 ms	19708 KB	Output is correct
15	Correct	1 ms	336 KB	Output is correct
16	Correct	10 ms	31824 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct
18	Correct	9 ms	31824 KB	Output is correct
19	Correct	4 ms	848 KB	Output is correct
20	Correct	8 ms	31568 KB	Output is correct
21	Correct	10 ms	31568 KB	Output is correct
22	Correct	4 ms	2896 KB	Output is correct
23	Correct	12 ms	31836 KB	Output is correct
24	Correct	3 ms	2896 KB	Output is correct
25	Correct	11 ms	31836 KB	Output is correct
26	Correct	11 ms	32036 KB	Output is correct
27	Correct	10 ms	31824 KB	Output is correct
28	Correct	12 ms	31824 KB	Output is correct
29	Correct	11 ms	31824 KB	Output is correct
30	Correct	14 ms	31824 KB	Output is correct
31	Correct	12 ms	31824 KB	Output is correct
32	Correct	12 ms	31824 KB	Output is correct
33	Correct	11 ms	32036 KB	Output is correct
34	Correct	12 ms	31824 KB	Output is correct
35	Correct	6 ms	17232 KB	Output is correct
36	Correct	6 ms	17232 KB	Output is correct
37	Correct	6 ms	17232 KB	Output is correct
38	Correct	4 ms	8784 KB	Output is correct
39	Correct	4 ms	8784 KB	Output is correct
40	Correct	15 ms	32140 KB	Output is correct
41	Correct	4 ms	8784 KB	Output is correct
42	Correct	18 ms	32276 KB	Output is correct
43	Correct	15 ms	32140 KB	Output is correct
44	Correct	1 ms	336 KB	Output is correct
45	Correct	204 ms	283188 KB	Output is correct
46	Correct	145 ms	272892 KB	Output is correct
47	Correct	205 ms	284152 KB	Output is correct
48	Correct	205 ms	299512 KB	Output is correct
49	Correct	60 ms	199164 KB	Output is correct
50	Correct	237 ms	292880 KB	Output is correct
51	Correct	217 ms	286712 KB	Output is correct
52	Correct	113 ms	276988 KB	Output is correct
53	Correct	58 ms	215548 KB	Output is correct
54	Correct	21 ms	3768 KB	Output is correct
55	Correct	247 ms	307184 KB	Output is correct
56	Correct	90 ms	273148 KB	Output is correct
57	Correct	109 ms	278268 KB	Output is correct
58	Correct	210 ms	273212 KB	Output is correct
59	Correct	97 ms	267516 KB	Output is correct
60	Correct	94 ms	260120 KB	Output is correct
61	Correct	221 ms	259308 KB	Output is correct
62	Correct	137 ms	296188 KB	Output is correct
63	Correct	162 ms	310268 KB	Output is correct
64	Correct	92 ms	304380 KB	Output is correct
65	Correct	207 ms	298232 KB	Output is correct
66	Correct	138 ms	303948 KB	Output is correct
67	Correct	166 ms	314620 KB	Output is correct
68	Correct	179 ms	314872 KB	Output is correct
69	Correct	194 ms	311288 KB	Output is correct
70	Correct	111 ms	310012 KB	Output is correct
71	Correct	187 ms	284664 KB	Output is correct
72	Correct	146 ms	280064 KB	Output is correct
73	Correct	185 ms	291576 KB	Output is correct
74	Correct	116 ms	283200 KB	Output is correct
75	Correct	83 ms	158344 KB	Output is correct
76	Correct	145 ms	282364 KB	Output is correct
77	Correct	189 ms	281592 KB	Output is correct
78	Correct	90 ms	159240 KB	Output is correct
79	Correct	77 ms	156412 KB	Output is correct
80	Correct	43 ms	78468 KB	Output is correct
81	Correct	89 ms	159232 KB	Output is correct
82	Correct	175 ms	251384 KB	Output is correct
83	Correct	37 ms	80524 KB	Output is correct
84	Correct	171 ms	256256 KB	Output is correct

답안 #1115866

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 12.0 / 12.0

Subtask #3 23.0 / 23.0

Subtask #4 38.0 / 38.0

Subtask #5 23.0 / 23.0

Subtask #1
4.0 / 4.0

Subtask #2
12.0 / 12.0

Subtask #3
23.0 / 23.0

Subtask #4
38.0 / 38.0

Subtask #5
23.0 / 23.0