답안 #953101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
953101	2024-03-25T13:50:55 Z	Sacharlemagne	Newspapers (CEOI21_newspapers)	C++17	6 / 100	217 ms	524288 KB

newspapers

#include <vector>
#include <iostream>
#include <queue>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int n,m,a,b; cin >> n >> m;

	vector<vector<int>> adj(n);
	while (m--) {
		cin >> a >> b;
		adj[--a].push_back(--b);
		adj[b].push_back(a);
	}
	vector<pair<int,int>> par(1 << n);
	queue<int> q; q.push((1<<n)-1);
	vector<int> dist(1<<n, 100); dist[(1<<n)-1] = 0;
	while (!q.empty()) {
		int node = q.front(); q.pop();
		int i = node;
		vector<int> access(n);
		for (int j = 0; j<n; ++j) {
			if (!(i & (1 << j))) continue;
			for (int u : adj[j]) ++access[u];
		}
		for (int on = 0; on<n; ++on) {
			int nei = 0;
			if (i && (1 << on)) {
				for (int u : adj[on]) {
					--access[u];
				}
			}
			for (int j = 0; j<n; ++j) if (access[j]) nei += (1 << j);
			if (i && (1 << on)) for (int u : adj[on]) ++access[u];
			if (nei == 0) {
				par[nei] = {node, on};
				vector<int> ans;
				while (nei != ((1 << n)-1)) {
					ans.push_back(par[nei].second);
					nei = par[nei].first;
				}
				cout << "YES\n";
				cout << dist[node]+1 << '\n';
				for (int i = ans.size()-1; i>=0;--i) cout << ans[i]+1 << ' ';
				return 0;
			}
			if (dist[nei] == 100) {
				par[nei] = {node, on};
				dist[nei] = dist[node]+1;
				q.push(nei);
			}
		}
 	}
	cout << "NO";
}

Compilation message

newspapers.cpp: In function 'int main()':
newspapers.cpp:29:16: warning: '<<' in boolean context, did you mean '<'? [-Wint-in-bool-context]
   29 |    if (i && (1 << on)) {
      |             ~~~^~~~~~
newspapers.cpp:35:16: warning: '<<' in boolean context, did you mean '<'? [-Wint-in-bool-context]
   35 |    if (i && (1 << on)) for (int u : adj[on]) ++access[u];
      |             ~~~^~~~~~

Subtask #1
6.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Partially correct	0 ms	348 KB	Failed to provide a successful strategy.
4	Partially correct	0 ms	348 KB	Failed to provide a successful strategy.
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	420 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Correct	1 ms	344 KB	Output is correct
20	Partially correct	0 ms	348 KB	Failed to provide a successful strategy.
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Partially correct	1 ms	348 KB	Failed to provide a successful strategy.
29	Correct	0 ms	348 KB	Output is correct
30	Correct	1 ms	348 KB	Output is correct
31	Correct	1 ms	604 KB	Output is correct
32	Correct	1 ms	604 KB	Output is correct
33	Correct	2 ms	856 KB	Output is correct
34	Correct	1 ms	604 KB	Output is correct
35	Correct	1 ms	856 KB	Output is correct
36	Correct	1 ms	604 KB	Output is correct
37	Correct	1 ms	604 KB	Output is correct
38	Correct	2 ms	604 KB	Output is correct
39	Correct	1 ms	1116 KB	Output is correct
40	Correct	2 ms	1112 KB	Output is correct
41	Correct	1 ms	1116 KB	Output is correct
42	Correct	2 ms	1116 KB	Output is correct
43	Correct	2 ms	1884 KB	Output is correct
44	Correct	2 ms	2012 KB	Output is correct
45	Correct	1 ms	1884 KB	Output is correct
46	Correct	1 ms	2132 KB	Output is correct
47	Correct	2 ms	3416 KB	Output is correct
48	Partially correct	3 ms	3420 KB	Failed to provide a successful strategy.
49	Correct	2 ms	3416 KB	Output is correct
50	Correct	2 ms	3420 KB	Output is correct
51	Correct	4 ms	6424 KB	Output is correct
52	Correct	3 ms	6492 KB	Output is correct
53	Correct	3 ms	6492 KB	Output is correct
54	Correct	3 ms	6492 KB	Output is correct
55	Correct	4 ms	12636 KB	Output is correct
56	Correct	5 ms	12636 KB	Output is correct
57	Correct	4 ms	12636 KB	Output is correct
58	Correct	4 ms	12636 KB	Output is correct
59	Correct	4 ms	12636 KB	Output is correct
60	Correct	4 ms	12636 KB	Output is correct
61	Correct	4 ms	12696 KB	Output is correct
62	Correct	4 ms	12636 KB	Output is correct
63	Correct	4 ms	12636 KB	Output is correct
64	Correct	4 ms	12636 KB	Output is correct

Subtask #2
0.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Partially correct	0 ms	348 KB	Failed to provide a successful strategy.
6	Partially correct	1 ms	344 KB	Failed to provide a successful strategy.
7	Partially correct	0 ms	348 KB	Failed to provide a successful strategy.
8	Partially correct	0 ms	348 KB	Failed to provide a successful strategy.
9	Partially correct	0 ms	348 KB	Failed to provide a successful strategy.
10	Partially correct	1 ms	464 KB	Failed to provide a successful strategy.
11	Runtime error	2 ms	2140 KB	Execution killed with signal 11
12	Halted	0 ms	0 KB	-

Subtask #3
0.0 / 80.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Partially correct	0 ms	348 KB	Failed to provide a successful strategy.
4	Partially correct	0 ms	348 KB	Failed to provide a successful strategy.
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	420 KB	Output is correct
8	Correct	0 ms	344 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	0 ms	344 KB	Output is correct
19	Correct	1 ms	344 KB	Output is correct
20	Partially correct	0 ms	348 KB	Failed to provide a successful strategy.
21	Correct	0 ms	348 KB	Output is correct
22	Correct	0 ms	348 KB	Output is correct
23	Correct	1 ms	348 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Partially correct	1 ms	348 KB	Failed to provide a successful strategy.
29	Correct	0 ms	348 KB	Output is correct
30	Correct	1 ms	348 KB	Output is correct
31	Correct	1 ms	604 KB	Output is correct
32	Correct	1 ms	604 KB	Output is correct
33	Correct	2 ms	856 KB	Output is correct
34	Correct	1 ms	604 KB	Output is correct
35	Correct	1 ms	856 KB	Output is correct
36	Correct	1 ms	604 KB	Output is correct
37	Correct	1 ms	604 KB	Output is correct
38	Correct	2 ms	604 KB	Output is correct
39	Correct	1 ms	1116 KB	Output is correct
40	Correct	2 ms	1112 KB	Output is correct
41	Correct	1 ms	1116 KB	Output is correct
42	Correct	2 ms	1116 KB	Output is correct
43	Correct	2 ms	1884 KB	Output is correct
44	Correct	2 ms	2012 KB	Output is correct
45	Correct	1 ms	1884 KB	Output is correct
46	Correct	1 ms	2132 KB	Output is correct
47	Correct	2 ms	3416 KB	Output is correct
48	Partially correct	3 ms	3420 KB	Failed to provide a successful strategy.
49	Correct	2 ms	3416 KB	Output is correct
50	Correct	2 ms	3420 KB	Output is correct
51	Correct	4 ms	6424 KB	Output is correct
52	Correct	3 ms	6492 KB	Output is correct
53	Correct	3 ms	6492 KB	Output is correct
54	Correct	3 ms	6492 KB	Output is correct
55	Correct	4 ms	12636 KB	Output is correct
56	Correct	5 ms	12636 KB	Output is correct
57	Correct	4 ms	12636 KB	Output is correct
58	Correct	4 ms	12636 KB	Output is correct
59	Correct	4 ms	12636 KB	Output is correct
60	Correct	4 ms	12636 KB	Output is correct
61	Correct	4 ms	12696 KB	Output is correct
62	Correct	4 ms	12636 KB	Output is correct
63	Correct	4 ms	12636 KB	Output is correct
64	Correct	4 ms	12636 KB	Output is correct
65	Correct	0 ms	348 KB	Output is correct
66	Correct	0 ms	348 KB	Output is correct
67	Partially correct	0 ms	348 KB	Failed to provide a successful strategy.
68	Partially correct	0 ms	348 KB	Failed to provide a successful strategy.
69	Correct	0 ms	348 KB	Output is correct
70	Correct	0 ms	344 KB	Output is correct
71	Correct	0 ms	348 KB	Output is correct
72	Correct	0 ms	348 KB	Output is correct
73	Correct	1 ms	348 KB	Output is correct
74	Correct	0 ms	348 KB	Output is correct
75	Correct	0 ms	348 KB	Output is correct
76	Correct	0 ms	348 KB	Output is correct
77	Correct	1 ms	348 KB	Output is correct
78	Correct	0 ms	348 KB	Output is correct
79	Runtime error	217 ms	524288 KB	Execution killed with signal 9
80	Halted	0 ms	0 KB	-

답안 #953101

Compilation message

Subtask #1 6.0 / 12.0

Subtask #2 0.0 / 8.0

Subtask #3 0.0 / 80.0

Subtask #1
6.0 / 12.0

Subtask #2
0.0 / 8.0

Subtask #3
0.0 / 80.0