oj.uz

Submission #595702

# Submission time Handle Problem Language Result Execution time Memory
595702 2022-07-14T01:40:00 Z penguinhacker Meetings 2 (JOI21_meetings2) C++17
0 / 100
 4 ms 5812 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 4 ms 5800 KB Output is correct
4 Correct 4 ms 5716 KB Output is correct
5 Correct 3 ms 5716 KB Output is correct
6 Correct 3 ms 5812 KB Output is correct
7 Incorrect 4 ms 5716 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 4 ms 5800 KB Output is correct
4 Correct 4 ms 5716 KB Output is correct
5 Correct 3 ms 5716 KB Output is correct
6 Correct 3 ms 5812 KB Output is correct
7 Incorrect 4 ms 5716 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 4 ms 5800 KB Output is correct
4 Correct 4 ms 5716 KB Output is correct
5 Correct 3 ms 5716 KB Output is correct
6 Correct 3 ms 5812 KB Output is correct
7 Incorrect 4 ms 5716 KB Output isn't correct
8 Halted 0 ms 0 KB -