oj.uz

Submission #953101

# Submission time Handle Problem Language Result Execution time Memory
953101 2024-03-25T13:50:55 Z Sacharlemagne Newspapers (CEOI21_newspapers) C++17
6 / 100
 217 ms 524288 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -