oj.uz

Submission #523292

# Submission time Handle Problem Language Result Execution time Memory
523292 2022-02-07T10:42:36 Z amunduzbaev Meetings 2 (JOI21_meetings2) C++17
0 / 100
 4 ms 5028 KB 
#include "bits/stdc++.h"
using namespace std;
 
#define ar array

const int N = 2e5 + 5;
vector<int> edges[N], tt;
int sub[N], n, C, d[N];
int used[N], ss[N], rr[N];

void dff(int u, int p = -1){
	ss[u] = 1;
	for(auto x : edges[u]){
		if(x == p) continue;
		dff(x, u);
		ss[u] += ss[x];
	}
}

void dfs(int u, int n, int p = -1){
	sub[u] = 1;
	if(p == -1) d[u] = 0;
	for(auto x : edges[u]){
		if(x == p) continue;
		if(!used[x]){
			d[x] = d[u] + 1;
			dfs(x, n, u);
			sub[u] += sub[x];
		} else {
			if(ss[u] > ss[x]) sub[u] += ss[x];
			else sub[u] += (::n - ss[u]);
		}
	}
	if(sub[u] > n / 2 && C == -1) C = u;
}

void get(int u, int p = -1){
	tt.push_back(u);
	for(auto x : edges[u]){
		if(used[x] || x == p) continue;
		get(x, u);
	}
}

void dec(int u, int n){
	C = -1;
	dfs(u, n), dfs(C, n);
	
	set<ar<int, 2>> ss;
	
	auto add = [&](ar<int, 2> x){
		auto it = ss.lower_bound({x[0] + 1, -1});
		if(it != ss.end()){
			if((*it)[1] >= x[1]) return;;
		}
		
		vector<ar<int, 2>> del;
		while(it != ss.begin()){
			it--;
			if((*it)[1] <= x[1]) del.push_back(*it);
			else break;
		}
		
		for(auto v : del) ss.erase(v);
		ss.insert(x);
	};
	
	for(auto x : edges[C]){
		if(used[x]) continue;
		tt.clear(); get(x, C);
		for(auto x : tt){
			auto it = ss.lower_bound({sub[x], -1});
			if(it != ss.end()){
				rr[sub[x]] = max(rr[sub[x]], d[x] + (*it)[1] + 1);
			}
		} for(auto x : tt) add({sub[x], d[x]});
	}
	
	reverse(edges[C].begin(), edges[C].end());
	ss.clear();
	for(auto x : edges[C]){
		if(used[x]) continue;
		tt.clear(); get(x, C);
		for(auto x : tt){
			auto it = ss.lower_bound({sub[x], -1});
			if(it != ss.end()){
				rr[sub[x]] = max(rr[sub[x]], d[x] + (*it)[1] + 1);
			}
			
			//~ n - (int)tt.size()
			rr[min(sub[x], n - (int)tt.size())] = 
			max(rr[min(sub[x], n - (int)tt.size())], d[x] + 1);
		} for(auto x : tt) add({sub[x], d[x]});
	}
	
	used[C] = 1;
	for(auto x : edges[u]){
		if(used[x]) continue;
		tt.clear(); get(x, C);
		dec(x, (int)tt.size());
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	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);
	}
	
	dff(1);
	dec(1, n);
	rr[n] = 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 3 ms 4944 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 2 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 5008 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 3 ms 5020 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 3 ms 5028 KB Output is correct
14 Correct 4 ms 4940 KB Output is correct
15 Correct 3 ms 4940 KB Output is correct
16 Correct 3 ms 4940 KB Output is correct
17 Correct 3 ms 5020 KB Output is correct
18 Correct 3 ms 4940 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Incorrect 2 ms 4940 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 2 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 5008 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 3 ms 5020 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 3 ms 5028 KB Output is correct
14 Correct 4 ms 4940 KB Output is correct
15 Correct 3 ms 4940 KB Output is correct
16 Correct 3 ms 4940 KB Output is correct
17 Correct 3 ms 5020 KB Output is correct
18 Correct 3 ms 4940 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Incorrect 2 ms 4940 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4944 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 2 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 5008 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 3 ms 4940 KB Output is correct
10 Correct 3 ms 4940 KB Output is correct
11 Correct 3 ms 5020 KB Output is correct
12 Correct 3 ms 4940 KB Output is correct
13 Correct 3 ms 5028 KB Output is correct
14 Correct 4 ms 4940 KB Output is correct
15 Correct 3 ms 4940 KB Output is correct
16 Correct 3 ms 4940 KB Output is correct
17 Correct 3 ms 5020 KB Output is correct
18 Correct 3 ms 4940 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Incorrect 2 ms 4940 KB Output isn't correct
21 Halted 0 ms 0 KB -