oj.uz

Submission #825812

# Submission time Handle Problem Language Result Execution time Memory
825812 2023-08-15T08:24:50 Z enerelt14 Newspapers (CEOI21_newspapers) C++14
8 / 100
 15 ms 24988 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;
	}
	if(n == 2) {
		cout << "YES\n2\n1 1";
		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 Correct 14 ms 24856 KB Output is correct
3 Correct 12 ms 24912 KB Output is correct
4 Correct 12 ms 24956 KB Output is correct
5 Partially correct 13 ms 24952 KB Failed to provide a successful strategy.
6 Partially correct 13 ms 24956 KB Failed to provide a successful strategy.
7 Correct 12 ms 24960 KB Output is correct
8 Partially correct 12 ms 24952 KB Failed to provide a successful strategy.
9 Incorrect 13 ms 24916 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24920 KB Output is correct
2 Correct 11 ms 24956 KB Output is correct
3 Correct 12 ms 24956 KB Output is correct
4 Correct 13 ms 24956 KB Output is correct
5 Correct 12 ms 24960 KB Output is correct
6 Correct 14 ms 24944 KB Output is correct
7 Correct 12 ms 24956 KB Output is correct
8 Correct 14 ms 24960 KB Output is correct
9 Correct 13 ms 24956 KB Output is correct
10 Correct 12 ms 24952 KB Output is correct
11 Correct 13 ms 24988 KB Output is correct
12 Correct 13 ms 24948 KB Output is correct
13 Correct 13 ms 24960 KB Output is correct
14 Correct 15 ms 24916 KB Output is correct
15 Correct 13 ms 24960 KB Output is correct
16 Correct 12 ms 24972 KB Output is correct
17 Correct 12 ms 24960 KB Output is correct
18 Correct 12 ms 24916 KB Output is correct
19 Correct 13 ms 24964 KB Output is correct
20 Correct 13 ms 24916 KB Output is correct

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 24916 KB Output is correct
2 Correct 14 ms 24856 KB Output is correct
3 Correct 12 ms 24912 KB Output is correct
4 Correct 12 ms 24956 KB Output is correct
5 Partially correct 13 ms 24952 KB Failed to provide a successful strategy.
6 Partially correct 13 ms 24956 KB Failed to provide a successful strategy.
7 Correct 12 ms 24960 KB Output is correct
8 Partially correct 12 ms 24952 KB Failed to provide a successful strategy.
9 Incorrect 13 ms 24916 KB Output isn't correct
10 Halted 0 ms 0 KB -