Submission #1073973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073973		sleepntsheep	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	0 ms	348 KiB

meetings2

#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", max(1, (r + 1) - (l - 1) + 1));
		}
	}
}

Compilation message (stderr)

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
• Subtask 2: 0 / 16
• Subtask 3: 0 / 80