oj.uz

Submission #825810

# Submission time Handle Problem Language Result Execution time Memory
825810 2023-08-15T08:23:26 Z enerelt14 Newspapers (CEOI21_newspapers) C++14
0 / 100
 14 ms 24956 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24916 KB Output is correct
2 Incorrect 13 ms 24956 KB Integer parameter [name=k] equals to 0, violates the range [1, 10]
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24916 KB Output is correct
2 Incorrect 14 ms 24848 KB Integer parameter [name=k] equals to 0, violates the range [1, 10]
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24916 KB Output is correct
2 Incorrect 13 ms 24956 KB Integer parameter [name=k] equals to 0, violates the range [1, 10]
3 Halted 0 ms 0 KB -