oj.uz

Submission #976515

# Submission time Handle Problem Language Result Execution time Memory
976515 2024-05-06T16:14:25 Z happy_node Meetings 2 (JOI21_meetings2) C++17
0 / 100
 3 ms 9820 KB 
#include <bits/stdc++.h>
using namespace std;

const int MX=2e5+5;
int N;
vector<int> adj[MX];

bool used[MX];
int sz[MX]; 
pair<int,int> f[MX], ff[MX]; // max_1, max_2

int getSize(int v, int p) {
	sz[v]=1;
	for(auto u:adj[v]) {
		if(u==p || used[u]) continue;
		sz[v]+=getSize(u,v);
	}
	return sz[v];
}

int getCen(int v, int p, int s) {
	for(auto u:adj[v]) {
		if(u==p || used[u]) continue;
		if(2*sz[u]>s) return getCen(u,v,s);
	}
	return v;
}

int head=0,s=0;
int ans[MX];

void dfs(int v, int p, int dep) {
	if(make_pair(dep,head)>f[sz[v]]) {
		ff[sz[v]]=f[sz[v]];
		f[sz[v]]=make_pair(dep,head);
	} else if(make_pair(dep,head)>ff[sz[v]]) {
		ff[sz[v]]=make_pair(dep,head);
	}

	{
		int i=min(sz[v],s-sz[head]);
		ans[2*i]=max(ans[2*i],dep+1);
	}

	for(auto u:adj[v]) {
		if(u==p || used[u]) continue;
		dfs(u,v,dep+1);
	}
}

void cdc(int v) {
	s=getSize(v,v);
	int cen=getCen(v,v,s);
	used[cen]=true;
	getSize(cen,cen);

	for(auto u:adj[cen]) {
		if(!used[u]) {
			head=u;
			dfs(u,cen,1);
		}
	}

	vector<pair<int,int>> vv;

	for(int i=s;i>=1;i--) {
		vv.push_back(f[i]);
		vv.push_back(ff[i]);
		sort(vv.rbegin(),vv.rend());

		while(vv.size()>3) vv.pop_back();

		for(int j=0;j<vv.size();j++) {
			for(int k=j+1;k<vv.size();k++) {
				if(vv[j].second!=vv[k].second)
					ans[2*i]=max(ans[2*i],vv[j].first+vv[k].first+1);
			}
			ans[2*i]=max(ans[2*i],vv[j].first+1);
		}
	}

	for(int i=1;i<=s;i++) {
		f[i]={0,0};
		ff[i]={0,0};
	}

	for(auto u:adj[cen]) {
		if(!used[u]) {
			cdc(u);
		}
	}
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin>>N;
	for(int i=1;i<N;i++) {
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	cdc(1);

	for(int i=N;i>=1;i--) {
		ans[i]=max(ans[i],ans[i+2]);
	}

	for(int i=1;i<=N;i++) {
		if(i&1) {
			cout<<1<<'\n';
		} else {
			cout<<ans[i]<<'\n';
		}
	}
}

Compilation message

meetings2.cpp: In function 'void cdc(int)':
meetings2.cpp:73:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |   for(int j=0;j<vv.size();j++) {
      |               ~^~~~~~~~~~
meetings2.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |    for(int k=j+1;k<vv.size();k++) {
      |                  ~^~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9816 KB Output is correct
4 Correct 2 ms 9672 KB Output is correct
5 Correct 2 ms 9680 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Incorrect 2 ms 9820 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9816 KB Output is correct
4 Correct 2 ms 9672 KB Output is correct
5 Correct 2 ms 9680 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Incorrect 2 ms 9820 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 2 ms 9816 KB Output is correct
4 Correct 2 ms 9672 KB Output is correct
5 Correct 2 ms 9680 KB Output is correct
6 Correct 2 ms 9820 KB Output is correct
7 Correct 2 ms 9820 KB Output is correct
8 Correct 3 ms 9820 KB Output is correct
9 Correct 2 ms 9820 KB Output is correct
10 Incorrect 2 ms 9820 KB Output isn't correct
11 Halted 0 ms 0 KB -