oj.uz

Submission #523229

# Submission time Handle Problem Language Result Execution time Memory
523229 2022-02-07T08:44:49 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]});
	
	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]) break;
			del.push_back(*it);
		}
		
		for(auto x : del) ss[u].erase(x);
		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] * 2] = max(rr[sub[u] * 2], d[u] - d[x] + 1);
	
	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]){
			add(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]){
			add(x);
		} ss[v].clear();
	}
	add({sub[u], d[u]});
	
	//~ 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, 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 8 ms 14412 KB Output is correct
2 Correct 7 ms 14340 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Incorrect 7 ms 14408 KB Output isn't correct
5 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 14340 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Incorrect 7 ms 14408 KB Output isn't correct
5 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 14340 KB Output is correct
3 Correct 7 ms 14412 KB Output is correct
4 Incorrect 7 ms 14408 KB Output isn't correct
5 Halted 0 ms 0 KB -