Submission #953100

#	Time	Username	Problem	Language	Result	Execution time	Memory
953100		Sacharlemagne	Newspapers (CEOI21_newspapers)	C++17	6 / 100	266 ms	524288 KiB

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; ans.reserve(dist[node]+1);
				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 (stderr)

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 / 12
• Subtask 2: 0 / 8
• Subtask 3: 0 / 80