oj.uz

Submission #1010205

# Submission time Handle Problem Language Result Execution time Memory
1010205 2024-06-28T13:10:22 Z PoPularPlusPlus Meetings 2 (JOI21_meetings2) C++17
0 / 100
 2 ms 7516 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(),x.end()
#define vf first 
#define vs second
const int mod = 1000000007;
 
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

const int N = 200004;
vector<int> adj[N];
int siz[N];
bool vis[N];
int ans[N];
int mx[N];

void cal_siz(int node , int par){
	siz[node] = 1;
	for(int i : adj[node]){
		if(i!=par && !vis[i]){
			cal_siz(i , node);
			siz[node] += siz[i];
		}
	}
}

int centroid(int node , int par , int tot){
	for(int i : adj[node]){
		if(!vis[i] && i != par && siz[i] >= tot){
			return centroid(i , node , tot);
		}
	}
	return node;
}

void dfs(int node , int par , int dis){
	mx[siz[node]] = max(mx[siz[node]] , dis);
	for(int i : adj[node]){
		if(i!=par && !vis[i])dfs(i , node , dis + 1);
	}
}

void centroid_decomposition(int node){
	cal_siz(node , node);
	int tot = siz[node];
	int root = centroid(node , node , (tot)/2);
	cal_siz(root,root);
	vector<pair<int,int>> v[tot + 2];
	int mx_siz = 0;
	for(int i : adj[root]){
		if(!vis[i]){
			mx_siz = max(mx_siz , siz[i]);
			for(int j = 0; j <= siz[i]; j++){
				mx[j] = -1;
			}
			dfs(i , root , 1);
			for(int j = 1; j <= siz[i]; j++){
				//cout << mx[j] << ' ';
				v[j].pb(mp(mx[j],i));
				sort(all(v[j]),greater<>());
				while(v[j].size() > 2)v[j].pop_back();
			}
			//cout << '\n';
		}
	}

	v[tot-mx_siz].pb(mp(0,-1));
	sort(all(v[tot-mx_siz]) , greater<>());
	while(v[tot-mx_siz].size() > 2)v[tot-mx_siz].pop_back();

	/*for(int i = tot; i >= 0; i--){
		cout << i << '\n';
		for(auto j : v[tot]){
			cout << j.vf << ' ' << j.vs << '\n';
		}
	}*/

	for(int i = tot; i > 0; i--){
		for(auto j : v[i + 1]){
			v[i].pb(j);
		}
		assert(v[i].size() <= 4);
		sort(all(v[i]),greater<>());
		if(v[i].size() >= 2){
			if(v[i][0].vs == v[i][1].vs){
				v[i].erase(v[i].begin() + 1);
			}
		}
		if(v[i].size() >= 2){
			if(v[i][0].vs == v[i][1].vs){
				v[i].erase(v[i].begin()+1);
			}
		}

		if(v[i].size() >= 2){
			if(v[i][0].vs == v[i][1].vs){
				v[i].erase(v[i].begin()+1);
			}
		}

		while(v[i].size() > 2)v[i].pop_back();

		if(v[i].size() >= 2 && v[i][0].vs != v[i][1].vs){
			ans[2*i] = max(ans[2*i] , v[i][0].vf + v[i][1].vf + 1); 
		}
	}
	vis[root] = 1;
	for(int i : adj[root]){
		if(!vis[i]){
			centroid_decomposition(i);
		}
	}
}

void solve(){
	int n;
	cin >> n;
	for(int i = 0; i < n - 1; i++){
		int a , b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	memset(vis,0,sizeof vis);
	memset(ans,-1,sizeof ans);

	centroid_decomposition(1);

	for(int i = n; i > 0; i--){
		if(i % 2 == 1){;}
		else {
			ans[i] = max(ans[i] , ans[i + 2]);
		}
	}
	for(int i = 1; i <= n; i++){
		if(i % 2 == 1)cout << 1 << '\n';
		else cout << ans[i] << '\n';
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	//int t;
	//cin >> t;
	//while(t--)
		solve();
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 1 ms 7516 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 1 ms 7516 KB Output is correct
5 Incorrect 1 ms 7512 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 1 ms 7516 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 1 ms 7516 KB Output is correct
5 Incorrect 1 ms 7512 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 1 ms 7516 KB Output is correct
3 Correct 1 ms 7516 KB Output is correct
4 Correct 1 ms 7516 KB Output is correct
5 Incorrect 1 ms 7512 KB Output isn't correct
6 Halted 0 ms 0 KB -