oj.uz

Submission #946764

# Submission time Handle Problem Language Result Execution time Memory
946764 2024-03-15T04:13:21 Z Halym2007 Newspapers (CEOI21_newspapers) C++17
8 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N = 1e3 + 5;
vector <int> v[N];
int uzyn[N], par[N], vis[N], bolonok, val, dia[N];

void dfs (int x, int pr) {
	for (int i : v[x]) {
		if (i == pr) continue;
		uzyn[i] = uzyn[x] + 1;
		par[i] = x;
		dfs (i, x);
	}
}

void barla (int x, int pr) {
	for (int i : v[x]) {
		if (i == pr) continue;
		if (dia[i]) continue;
		val++;
		if (val >= 3) bolonok = 1;
		barla (i, x);
		val--;
	}
}


int main () {
//	freopen ("input.txt", "r", stdin);
	int n, m, subtask1 = 0;
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int l, r;
		cin >> l >> r;
		v[l].pb (r);
		v[r].pb (l);
		if (r - l != 1) subtask1 = 1;
	}
	if (m >= n) {
		cout << "NO\n";
	}
	else if (n <= 2) {
		cout << "YES\n";
		cout << n << "\n";
		for (int i = 1; i <= n; ++i) {
			cout << n << " ";
		}
	}
	else if (!subtask1) {
		cout << "YES\n";
		cout << 2*n - 4 << "\n";
		for (int i = 2; i < n; ++i) {
			cout << i << " ";
		}
		for (int i = n - 1; i > 1; i--) {
			cout << i << " ";
		}
	}
	else {
		assert (1 == -1);
		dfs (1, -1);
		int a = 0;
		for (int i = 1; i <= n; ++i) {
			if (uzyn[a] < uzyn[i]) a = i;
 		}
 		uzyn[a] = 0;
 		par[a] = -1;
 		dfs (a, -1);
 		int b = 0;
 		for (int i = 1; i <= n; ++i) {
 			if (uzyn[b] < uzyn[i]) b = i;
		}
		int x = b;
		while (x != -1) {
			vis[x] = 1;
			x = par[x];
		}
		for (int i = 1; i <= n; ++i) {
			if (vis[i]) {
				val = 0;
				barla(i, -1);
			}
		}
//		cout << "men";
		if (bolonok) cout << "NO";
		else cout << "YES";
		cout << "\n";
	}
}

Subtask #1
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Runtime error 1 ms 604 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

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

Subtask #3
0.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Runtime error 1 ms 604 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -