Submission #595702

#	Time	Username	Problem	Language	Result	Execution time	Memory
595702		penguinhacker	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	4 ms	5812 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=2e5;
int n, d[mxN], p1, p2, s[mxN];
vector<int> adj[mxN];
deque<int> path;

int bfs(int source) {
	int last=source;
	memset(d, -1, sizeof(d));
	d[source]=0;
	queue<int> q({source});
	for (; q.size(); q.pop()) {
		int u=q.front();
		last=u;
		for (int v : adj[u])
			if (d[v]==-1) {
				d[v]=d[u]+1;
				q.push(v);
			}
	}
	return last;
}

bool dfs1(int u=p1, int p=-1) {
	path.push_back(u);
	if (u==p2)
		return 1;
	for (int v : adj[u])
		if (v!=p&&dfs1(v, u))
			return 1;
	path.pop_back();
	return 0;
}

void dfs2(int u=p1, int p=-1) {
	s[u]=1;
	for (int v : adj[u])
		if (v!=p)
			dfs2(v, u), s[u]+=s[v];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i=1; i<n; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	p1=bfs(0), p2=bfs(p1);
	dfs1();
	dfs2();
	for (int i=1; i<=n; ++i) {
		if (i%2) {
			cout << "1\n";
			continue;
		}
		while(path.size()>1&&s[path.back()]<i/2)
			path.pop_back();
		while(path.size()>1&&n-s[path[1]]<i/2)
			path.pop_front();
		cout << path.size() << "\n";
	}
	return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 16
• Subtask 3: 0 / 80