oj.uz

Submission #576540

# Submission time Handle Problem Language Result Execution time Memory
576540 2022-06-13T07:27:41 Z 8e7 Newspapers (CEOI21_newspapers) C++17
8 / 100
 12 ms 468 KB 
//Challenge: Accepted
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1005
#define mod 998244353
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> adj[maxn], g[maxn];

int getdep(int n, int par) {
	int ret = 1;
	for (int v:adj[n]) {
		if (v != par) {
			ret = max(ret, getdep(v, n) + 1);
		}
	}
	return ret;
}

bool path[maxn];
void getpath(int n, int par) {
	path[n] = 1;
	bool to = 0;
	for (int v:g[n]) {
		if (v != par && g[v].size() > 1) {
			getpath(v, n);
			to = 1;
			break;
		}
	}
	if (to == 0) {
		for (int v:g[n]) {
			if (v != par) {
				getpath(v, n);
				break;
			}
		}
	}
}
vector<int> ans;
int last = 0;
void solve(int n, int par) {
	ans.push_back(n);
	last = n;
	for (int v:g[n]) {
		if (v != par && !path[v]) {
			ans.push_back(v);
			ans.push_back(n);
		}
	}
	for (int v:g[n]) {
		if (v != par && path[v]) {
			solve(v, n);
		}
	}
}
int main() {
	io
	int n, m;
	cin >> n >> m;
	for (int i = 0;i < m;i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	if (m > n - 1) {
		cout << "NO\n";
		return 0;
	}
	vector<int> nodes;
	for (int i = 1;i <= n;i++) {
		int cnt = 0;
		for (int v:adj[i]) {
			if (getdep(v, i) >= 3) cnt++;
		}
		if (cnt > 2) {
			cout << "NO\n";
			return 0;
		}
		if (adj[i].size() > 1) {
			nodes.push_back(i);
			for (int v:adj[i]) {
				if (adj[v].size() > 1) {
					g[i].push_back(v);
				}
			}
		}
	}	
	cout << "YES\n";
	if (nodes.size() == 0) {
		ans.push_back(1);
		if (n > 1) ans.push_back(1);
	} else if (nodes.size() == 1) {
		ans.push_back(nodes[0]);	
		ans.push_back(nodes[0]);	
	} else {
		for (int i:nodes) {
			if (g[i].size() == 1 && g[g[i][0]].size() <= 2) {
				getpath(i, 0);
				solve(i, 0);
				break;
			}
		}
		solve(last, 0);
	}
	cout << ans.size() << "\n";
	for (int i:ans) cout << i << " ";
	cout << "\n";
}

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Incorrect 0 ms 340 KB Integer 0 violates the range [1, 7]
9 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 10 ms 452 KB Output is correct
12 Correct 4 ms 468 KB Output is correct
13 Correct 4 ms 468 KB Output is correct
14 Correct 5 ms 468 KB Output is correct
15 Correct 5 ms 468 KB Output is correct
16 Correct 11 ms 428 KB Output is correct
17 Correct 12 ms 468 KB Output is correct
18 Correct 11 ms 448 KB Output is correct
19 Correct 11 ms 460 KB Output is correct
20 Correct 11 ms 468 KB Output is correct

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Incorrect 0 ms 340 KB Integer 0 violates the range [1, 7]
9 Halted 0 ms 0 KB -