Submission #825810

#	Time	Username	Problem	Language	Result	Execution time	Memory
825810		enerelt14	Newspapers (CEOI21_newspapers)	C++14	0 / 100	14 ms	24956 KiB

newspapers

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#define pb push_back
using namespace std;

int n, m;
vector<int> adj[1005], res[1048576];
bool vis[1048576];

vector<int> solve(int mask) {
	if(vis[mask]) return res[mask];
	vis[mask] = 1;
	if(!mask) return res[mask];
	res[mask].pb(-1);
	for(int i = 0; i < n; i++) {
		if(!(mask & (1 << i))) continue;
		int bitmask = 0;
		for(int j = 0; j < n; j++) {
			if(!(mask & (1 << j)) || i == j) continue;
			for(int k = 0; k < (int)adj[j].size(); k++) bitmask |= (1 << adj[j][k]);
		}
		vector<int> x = solve(bitmask);	
		if((int)x.size() > 0 && x[0] == -1) continue;
		if(res[mask][0] == -1) {
			res[mask].pop_back();
			res[mask].pb(i + 1);
			for(int i = 0; i < (int)x.size(); i++) res[mask].pb(x[i]);
			continue;
		}
		if((int)res[mask].size() <= (int)x.size() + 1) continue;
		res[mask].clear();
		res[mask].pb(i + 1);
		for(int i = 0; i < (int)x.size(); i++) res[mask].pb(x[i]);
	}
	return res[mask];
}

void go() {
	vector<int> ans = solve((1 << n) - 1);
	if(ans[0] == -1) {
		cout << "NO\n";
		return;
	}
	cout << "YES\n";
	cout << (int)ans.size() << "\n";
	for(int i = 0; i < (int)ans.size(); i++) {
		cout << ans[i] << " ";
	}
}

int main() {
	cin >> n >> m;
	if(m >= n) {
		cout << "NO\n";
		return 0;
	}
	if(n == 1) {
		cout << "YES\n1\n1";
		return 0;
	}
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	// if(n <= 20) {
	// 	go();
	// 	return 0;
	// }
	cout << "YES\n";
	cout << 2 * (n - 2) << "\n";
	for(int i = 2; i < n; i++) {
		cout << i << " ";
	}
	for(int i = n - 1; i > 1; i--) {
		cout << i << " ";
	}
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 8
• Subtask 3: 0 / 80