oj.uz

Submission #1073972

# Submission time Handle Problem Language Result Execution time Memory
1073972 2024-08-25T05:42:08 Z sleepntsheep Meetings 2 (JOI21_meetings2) C++17
0 / 100
 1 ms 348 KB 
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

template <typename T>
using ve = vector<T>;

int main() {
	int n;
	scanf("%d", &n);
	ve<ve<int> > g(n);
	for (int u, v, i = 1; i < n; ++i)
		scanf("%d%d", &u, &v), --u, --v, g[u].push_back(v), g[v].push_back(u);


	auto dfs = [&](auto dfs, int u, int p, ve<int> &dep) -> void {
		for (auto v : g[u]) if (v != p) dep[v] = dep[u] + 1, dfs(dfs, v, u, dep);
	};

	ve<int> dep(n), eep(n);
	dfs(dfs, 0, 0, dep);
	int a = (int)(max_element(dep.begin(), dep.end()) - dep.begin());
	dep.assign(n, 0);
	dfs(dfs, a, a, dep);
	int b = (int)(max_element(dep.begin(), dep.end()) - dep.begin());
	dfs(dfs, b, b, eep);

	auto lik = [&](int i) { return dep[i] + eep[i] == eep[a]; };
	ve<int> pat;
	for (int i = 0; i < n; ++i) if (lik(i)) pat.push_back(i);
	sort(pat.begin(), pat.end(), [&](int i, int j){ return dep[i] < dep[j]; });

	ve<int> ww(n, 1);

	auto efs = [&](auto efs, int u, int p, int rt) -> void {
		++ww[rt];
		for (auto v : g[u]) if (p != v && !lik(v)) efs(efs, v, u, rt);
	};
	for (auto x : pat) for (auto y : g[x]) if (!lik(y)) efs(efs, y, y, x);

	int l = 0, r = (int)pat.size() - 1, ls = 0, rs = 0;

	for (int i = 1; i <= n; ++i) {
		if (i & 1) puts("1");
		else {
			while (ls < i / 2 && l < (int)pat.size()) {
				ls += ww[pat[l++]];
			}
			while (rs < i / 2 && r >= 0) {
				rs += ww[pat[r--]];
			}
			printf("%d\n", (r + 1) - (l - 1) + 1);
		}
	}
}

Compilation message

meetings2.cpp: In function 'int main()':
meetings2.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
meetings2.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   scanf("%d%d", &u, &v), --u, --v, g[u].push_back(v), g[v].push_back(u);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -