oj.uz

Submission #523219

# Submission time Handle Problem Language Result Execution time Memory
523219 2022-02-07T08:36:37 Z amunduzbaev Meetings 2 (JOI21_meetings2) C++17
0 / 100
 8 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<<1];

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

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);
	dfs1(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"; continue; }
		cout<<rr[i]<<"\n";
	}
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 16.0

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

Subtask #3
0 / 80.0

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