oj.uz

Submission #543261

# Submission time Handle Problem Language Result Execution time Memory
543261 2022-03-30T02:12:39 Z LittleCube Meetings 2 (JOI21_meetings2) C++14
4 / 100
 7 ms 5332 KB 
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int N, ans[200005], sz[200005], dis[200005], vis[2000005], pre[200005];
vector<int> E[200005], cur;
pii res[200005][2];

void update(int i, pii p)
{
	if(p.S == res[i][0].S)
		res[i][0].F = max(res[i][0].F, p.F);
	else if(p.S == res[i][1].S)
		res[i][1].F = max(res[i][1].F, p.F);
	else if(p.F >= res[i][0].F)
	{
		res[i][1] = res[i][0];
		res[i][0] = p;
	}
	else if(p.F >= res[i][1].F)
		res[i][1] = p;
}

void dfs(int k, int r)
{
	cur.emplace_back(k);
	vis[k] = 1;
	sz[k] = 1;
	for(int i : E[k])
		if(!vis[i])
		{
			pre[i] = k;
			dis[i] = dis[k] + 1;
			dfs(i, r);
			sz[k] += sz[i];
		}
	vis[k] = 0;
	update(sz[k], {dis[k], r});
}

void cdec(int k)
{
	cur.clear();
	pre[k] = 0;
	dfs(k, k);
	int c = 0, ccnt = 0, M = sz[k];
	for(int i : cur)
	{
		bool valid = (M - sz[i] <= M / 2);
		for(int j : E[i])
			if(j != pre[i] && !vis[j])
				valid &= (sz[j] <= M / 2);
			
		if(valid)
			c = i, ccnt++;
	}
	if(ccnt == 2)
		ans[M] = max(2, ans[M]);

	assert(ccnt <= 2);

	cur.clear();
	for(int i = 1; i <= M / 2; i++)
		res[i][0] = res[i][1] = {0, c};

	vis[c] = 1;
	for(int i : E[c]) 
		if(!vis[i])
		{
			dis[i] = 1;
			dfs(i, i);
		}

	for(int i = M / 2; i >= 1; i--)
	{
		ans[i * 2] = max(ans[i * 2], res[i][0].F + res[i][1].F + 1);
		update(i - 1, res[i][0]);
		update(i - 1, res[i][1]);
	}

	for(int i : E[c])
		if(!vis[i])
			cdec(i);
}



signed main()
{
	cin >> N;
	for(int i = 1; i < N; i++)
	{
		int u, v;
		cin >> u >> v;
		E[u].emplace_back(v);
		E[v].emplace_back(u);
	}
	cdec(1);
	for(int i = 1; i <= N; i++)
		cout << max(1, ans[i]) << '\n';
}

Subtask #1
4.0 / 4.0

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

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 3 ms 4980 KB Output is correct
6 Correct 3 ms 5012 KB Output is correct
7 Correct 3 ms 5012 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 5008 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Incorrect 7 ms 5332 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5008 KB Output is correct
5 Correct 3 ms 4980 KB Output is correct
6 Correct 3 ms 5012 KB Output is correct
7 Correct 3 ms 5012 KB Output is correct
8 Correct 3 ms 4948 KB Output is correct
9 Correct 3 ms 5008 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 3 ms 4948 KB Output is correct
12 Correct 3 ms 4948 KB Output is correct
13 Correct 3 ms 4948 KB Output is correct
14 Correct 3 ms 4948 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 3 ms 4948 KB Output is correct
18 Correct 3 ms 4948 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Correct 3 ms 4948 KB Output is correct
22 Incorrect 7 ms 5332 KB Output isn't correct
23 Halted 0 ms 0 KB -