oj.uz

Submission #659717

# Submission time Handle Problem Language Result Execution time Memory
659717 2022-11-19T06:31:07 Z Sohsoh84 Newspapers (CEOI21_newspapers) C++17
0 / 100
 37 ms 50404 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 20;

int n, m, dist[1 << MAXN], t[1 << MAXN], r[1 << MAXN];
vector<int> adj[MAXN];
vector<pll> badj[1 << MAXN];

inline int f(int mask, int v) {
	mask = (mask | (1 << v)) ^ (1 << v);
	return r[mask];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	if (m >= n) return cout << "NO" << endl, 0;

	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		adj[u - 1].push_back(v - 1);
		adj[v - 1].push_back(u - 1);
	}

	for (int mask = 0; mask < (1 << n); mask++)
		for (int i = 0; i < n; i++)
			if (mask & (1 << i))
				for (int u : adj[i])
					r[mask] |= (1 << u);

	for (int mask = 1; mask < (1 << n); mask++)
		for (int i = 0; i < n; i++)
			badj[f(mask, i)].push_back({mask, i});

	memset(dist, 63, sizeof dist);
	queue<int> q;

	dist[0] = 0;
	q.push(0);

	while (!q.empty()) {
		int v = q.front();
		q.pop();

		for (auto [u, x] : badj[v]) {
			if (dist[u] > dist[v] + 1) {
				dist[u] = dist[v] + 1;
				t[u] = x;
				q.push(u);
			}
		}
	}

	int mask = (1 << n) - 1;
	if (dist[mask] > MAXN * MAXN) return cout << "YES" << endl, 0;

	cout << "YES" << endl << dist[mask] << endl;
	while (mask) {
		cout << t[mask] + 1 << sep;
		mask = f(mask, t[mask]);
	}

	cout << endl;
	return 0;
}

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29012 KB Output is correct
2 Correct 14 ms 28948 KB Output is correct
3 Correct 14 ms 29012 KB Output is correct
4 Correct 14 ms 29012 KB Output is correct
5 Correct 15 ms 28972 KB Output is correct
6 Correct 14 ms 29012 KB Output is correct
7 Correct 13 ms 24916 KB Output is correct
8 Correct 14 ms 29012 KB Output is correct
9 Incorrect 14 ms 29112 KB Unexpected end of file - int32 expected
10 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 29140 KB Output is correct
2 Correct 14 ms 29048 KB Output is correct
3 Correct 14 ms 29056 KB Output is correct
4 Correct 17 ms 29024 KB Output is correct
5 Correct 14 ms 29036 KB Output is correct
6 Correct 14 ms 29012 KB Output is correct
7 Correct 15 ms 29008 KB Output is correct
8 Correct 14 ms 29060 KB Output is correct
9 Correct 14 ms 29012 KB Output is correct
10 Correct 15 ms 29128 KB Output is correct
11 Runtime error 37 ms 50404 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 14 ms 29012 KB Output is correct
2 Correct 14 ms 28948 KB Output is correct
3 Correct 14 ms 29012 KB Output is correct
4 Correct 14 ms 29012 KB Output is correct
5 Correct 15 ms 28972 KB Output is correct
6 Correct 14 ms 29012 KB Output is correct
7 Correct 13 ms 24916 KB Output is correct
8 Correct 14 ms 29012 KB Output is correct
9 Incorrect 14 ms 29112 KB Unexpected end of file - int32 expected
10 Halted 0 ms 0 KB -