oj.uz

Submission #523269

# Submission time Handle Problem Language Result Execution time Memory
523269 2022-02-07T09:43:51 Z amunduzbaev Meetings 2 (JOI21_meetings2) C++17
0 / 100
 9 ms 14412 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array

const int N = 2e5 + 5;
vector<int> edges[N];
set<ar<int, 2>> ss[N];
int sub[N], d[N], par[N][20];

void dfs(int u, int p = -1){
	sub[u] = 1;
	par[u][0] = p;
	for(int j=1;j<20;j++) par[u][j] = par[par[u][j-1]][j-1];
	for(auto x : edges[u]){
		if(x == p) continue;
		d[x] = d[u] + 1;
		dfs(x, u);
		sub[u] += sub[x];
	}
}

int rr[N];

void dfs1(int u, int p = -1){
	//~ ss[u].insert({sub[u], d[u]});
	
	auto add = [&](ar<int, 2> x){
		auto it = ss[u].lower_bound({x[0] + 1, -1});
		if(it != ss[u].end()){
			if((*it)[1] >= x[1]) return;;
		}
		
		vector<ar<int, 2>> del;
		while(it != ss[u].begin()){
			it--;
			if((*it)[1] <= x[1]) del.push_back(*it);
			else break;
		}
		
		for(auto v : del) ss[u].erase(v);
		ss[u].insert(x);
	};
	
	int x = u;
	for(int j=19;~j;j--){
		if(sub[1] - sub[par[x][j]] > sub[u]) x = par[x][j];
	} x = par[x][0];
	rr[sub[u]] = max(rr[sub[u]], d[u] - d[x] + 1);
	
	for(auto v : edges[u]){
		if(v == p) continue;
		dfs1(v, u);
		
		for(auto x : ss[v]){
			auto it = ss[u].lower_bound({x[0], -1});
			if(it != ss[u].end()){
				rr[x[0]] = max(rr[x[0]], (*it)[1] + x[1] - d[u] * 2 + 1);
			}
			add(x);
			if(x[0] > sub[1] - sub[v]){
				rr[sub[1] - sub[v]] = max(rr[sub[1] - sub[v]], x[1] - d[u] + 1);
			}
		}
	}
	
	reverse(edges[u].begin(), edges[u].end());
	ss[u].clear();
	
	for(auto v : edges[u]){
		if(v == p) continue;
		for(auto x : ss[v]){
			auto it = ss[u].lower_bound({x[0], -1});
			if(it != ss[u].end()){
				rr[x[0]] = max(rr[x[0]], (*it)[1] + x[1] - d[u] * 2 + 1);
			}
			add(x);
		}
	}
	
	add({sub[u], d[u]});
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	for(int i=1;i<n;i++){
		int a, b; cin>>a>>b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	
	dfs(1, 1);
	dfs1(1, 1);
	for(int i=n;i>0;i--){
		rr[i] = max(rr[i], rr[i+1]);
	}
	for(int i=1;i<=n;i++){
		if(i&1) cout<<1<<"\n"; 
		else cout<<rr[i/2]<<"\n";
	}
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 7 ms 14412 KB Output is correct
3 Incorrect 9 ms 14412 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 7 ms 14412 KB Output is correct
3 Incorrect 9 ms 14412 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14412 KB Output is correct
2 Correct 7 ms 14412 KB Output is correct
3 Incorrect 9 ms 14412 KB Output isn't correct
4 Halted 0 ms 0 KB -