oj.uz

Submission #827372

# Submission time Handle Problem Language Result Execution time Memory
827372 2023-08-16T11:59:19 Z NK_ Newspapers (CEOI21_newspapers) C++17
4 / 100
 1 ms 468 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using vi = V<int>;
using ll = long long;
using pi = pair<int, int>;
using vpi = V<pi>;
using vl = V<ll>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
 	
	int N, M; cin >> N >> M;

	if (M != N - 1) {
		cout << "NO" << nl;
		return 0;
	}

	V<vi> adj(N); for(int i = 0; i < M; i++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	vi leaf(N);

	int R = 0;
	function<void(int, int)> dfs = [&](int u, int p) {
		leaf[u] = 1;

		int ADJ = 0;
		for(auto& v : adj[u]) if (v != p) {
			leaf[u] = 0; dfs(v, u);
			if (!leaf[v]) ADJ++;
		}

		if (!leaf[u] && ADJ == 1) R = u;

		if (ADJ > 2) {
			cout << "NO" << nl;
			exit(0-0);
		}
	};

	dfs(0, -1);

	vi ans;
	function<void(int, int)> answer = [&](int u, int p) {
		bool has = 0;
		for(auto& v : adj[u]) if (v != p) {
			if (leaf[v]) { has = 1; continue; }
			else {
				dfs(v, u);
			}
		}

        ans.pb(u);
		if (has) ans.pb(u);
	};

	answer(R, -1);

	cout << "YES" << nl;
	cout << sz(ans) << nl;
	for(auto& x : ans) cout << x + 1 << " ";
	cout << nl;

	exit(0-0);
}

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Partially correct 0 ms 212 KB Failed to provide a successful strategy.
4 Partially correct 0 ms 212 KB Failed to provide a successful strategy.
5 Correct 0 ms 212 KB Output is correct
6 Partially correct 1 ms 212 KB Failed to provide a successful strategy.
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
4.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Partially correct 0 ms 212 KB Failed to provide a successful strategy.
4 Partially correct 0 ms 212 KB Failed to provide a successful strategy.
5 Partially correct 0 ms 212 KB Failed to provide a successful strategy.
6 Partially correct 0 ms 212 KB Failed to provide a successful strategy.
7 Partially correct 0 ms 212 KB Failed to provide a successful strategy.
8 Partially correct 0 ms 212 KB Failed to provide a successful strategy.
9 Partially correct 0 ms 212 KB Failed to provide a successful strategy.
10 Partially correct 0 ms 212 KB Failed to provide a successful strategy.
11 Partially correct 1 ms 468 KB Failed to provide a successful strategy.
12 Partially correct 0 ms 340 KB Failed to provide a successful strategy.
13 Partially correct 0 ms 340 KB Failed to provide a successful strategy.
14 Partially correct 0 ms 340 KB Failed to provide a successful strategy.
15 Partially correct 0 ms 340 KB Failed to provide a successful strategy.
16 Partially correct 1 ms 468 KB Failed to provide a successful strategy.
17 Partially correct 1 ms 468 KB Failed to provide a successful strategy.
18 Partially correct 1 ms 468 KB Failed to provide a successful strategy.
19 Partially correct 1 ms 468 KB Failed to provide a successful strategy.
20 Partially correct 1 ms 468 KB Failed to provide a successful strategy.

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Partially correct 0 ms 212 KB Failed to provide a successful strategy.
4 Partially correct 0 ms 212 KB Failed to provide a successful strategy.
5 Correct 0 ms 212 KB Output is correct
6 Partially correct 1 ms 212 KB Failed to provide a successful strategy.
7 Correct 0 ms 212 KB Output is correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Halted 0 ms 0 KB -