oj.uz

답안 #394206

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
394206 2021-04-26T06:06:47 Z oolimry Meetings 2 (JOI21_meetings2) C++17
0 / 100
 3 ms 4948 KB 
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int) x.size())
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x, y) cerr << #x << " is " << x << ", " << #y << " is " << y << endl;
typedef long long lint;
typedef pair<lint, lint> ii;

int ans[200005];
vector<int> adj[200005];
bool cented[200005];
int sz[200005];
int dis[200005];
vector<int> nodes;

void dfs(int u, int p){
	nodes.push_back(u);
	sz[u] = 1;
	for(int v : adj[u]){
		if(cented[v] or v == p) continue;
		dis[v] = dis[u]+1;
		dfs(v, u);
		sz[u] += sz[v];
	}
}
void init(int u, int p = -1){
	dis[u] = 0;
	nodes.clear();
	dfs(u,p);
}


struct thing{ int sub, dis, sz; };

void recurse(int R){
	init(R, -1);
	
	int cent = -1;
	for(int u : nodes){
		int maxsz = sz[R] - sz[u];
		for(int v : adj[u]){
			if(cented[v] or sz[v] > sz[u]) continue;
			maxsz = max(maxsz, sz[v]);
		}
		if(maxsz <= sz(nodes)/2){
			cent = u;
			break;
		}
	}
	
	vector<thing> stuff;
	
	int total = sz[R];
	for(int v : adj[cent]){
		if(cented[v]) continue;
		init(v, cent);
		for(int x : nodes){
			stuff.push_back({v, dis[x], sz[x]});
		}
	}
	
	sort(all(stuff), [&](thing &a, thing &b){ return a.sz > b.sz; });
	
	ii b1 = {-1, -1}, b2 = {-2, -2};
	for(thing &s : stuff){
		///if root is the endpoint
		int SZ = 2*min(s.sz, total-s.sz);
		ans[SZ] = max(ans[SZ], s.dis+2);
		//show2(s.sub, s.dis);
		
		///if root is not endpoint
		int best = b1.first;
		if(b1.second == s.sub) best = b2.first;
		ans[2*s.sz] = max(ans[2*s.sz], best+s.dis+3);
		
		ii cur = ii(s.dis, s.sub);
		if(b1.second == cur.second) b1 = max(b1, cur);
		else b2 = max(b2, cur);
		if(b1 < b2) swap(b1, b2);
	}
	
	cented[cent] = true;
	for(int v : adj[cent]){
		if(cented[v]) continue;
		recurse(v);
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n; cin >> n;
	for(int i = 1;i < n;i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	fill(ans, ans+n+1, 1);
	
	recurse(1);
	
	for(int i = ((n&1)^1);i >= 2;i -= 2) ans[i] = max(ans[i], ans[i+2]);
	for(int i = 1;i <= n;i++) cout << ans[i] << "\n";
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Incorrect 3 ms 4940 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Incorrect 3 ms 4940 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Incorrect 3 ms 4940 KB Output isn't correct
5 Halted 0 ms 0 KB -