oj.uz

답안 #1042080

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1042080 2024-08-02T14:11:01 Z pcc Meetings 2 (JOI21_meetings2) C++17
100 / 100
 441 ms 34424 KB 
#include <bits/stdc++.h>
using namespace std;


const int mxn = 4e5+10;
vector<int> tree[mxn];
bitset<mxn> del;
int sz[mxn],dep[mxn];
int N;
int ans[mxn];

struct BIT{
	int bit[mxn];
	int s;
	void resize(int n){
		s = n;
		fill(bit,bit+s+1,-mxn);
	}
	void modify(int p,int v){
		p = s-p;
		assert(p>0);
		for(;p<s;p+=p&-p)bit[p] = max(bit[p],v);
	}
	int getval(int p){
		p = s-p;
		int re = -mxn;
		for(;p>0;p-= p&-p)re = max(re,bit[p]);
		return re;
	}
};

BIT bit;

void szdfs(int now,int par){
	sz[now] = 1;
	for(auto nxt:tree[now]){
		if(nxt == par||del[nxt])continue;
		szdfs(nxt,now);
		sz[now] += sz[nxt];
	}
	return;
}
int find_centroid(int now,int par,int tar){
	for(auto nxt:tree[now]){
		if(nxt == par||del[nxt])continue;
		if(sz[nxt]>tar)return find_centroid(nxt,now,tar);
	}
	return now;
}

void dfs(int now,int par,int psz){
	if(now == par)dep[now] = 1;
	for(auto nxt:tree[now]){
		if(nxt == par||del[nxt])continue;
		dep[nxt] = dep[now]+1;
		dfs(nxt,now,psz);
	}
	int pos = sz[now];
	ans[pos*2] = max(ans[pos*2],dep[now]+bit.getval(pos)+1);
	ans[min(psz,pos)*2] = max(ans[min(psz,pos)*2],dep[now]+1);
	return;
}
void dfs2(int now,int par){
	bit.modify(sz[now],dep[now]);
	for(auto nxt:tree[now]){
		if(nxt == par||del[nxt])continue;
		dfs2(nxt,now);
	}
	return;
}

void cd(int now,int par){
	dep[now] = 0;
	szdfs(now,now);
	bit.resize(sz[now]+3);
	now = find_centroid(now,now,(sz[now]-1)>>1);
	szdfs(now,now);
	del[now] = true;
	for(auto nxt:tree[now]){
		if(del[nxt])continue;
		dep[nxt] = 1;
		dfs(nxt,nxt,N-sz[nxt]);
		dfs2(nxt,nxt);
	}
	bit.resize(sz[now]+3);
	for(auto it = tree[now].rbegin();it != tree[now].rend();it++){
		int nxt = *it;
		if(del[nxt])continue;
		dep[nxt] = 1;
		dfs(nxt,nxt,N-sz[nxt]);
		dfs2(nxt,nxt);
	}
	for(auto nxt:tree[now]){
		if(!del[nxt])cd(nxt,now);
	}
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	fill(ans,ans+N+1,1);
	for(int i = 1;i<N;i++){
		int a,b;
		cin>>a>>b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	cd(1,1);
	for(int i = N;i>=1;i--)ans[i] = max(ans[i],ans[i+1]);
	for(int i = 1;i<=N;i+=2)ans[i] = 1;
	for(int i = 1;i<=N;i++)cout<<ans[i]<<'\n';
	return 0;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 15964 KB Output is correct
2 Correct 2 ms 15964 KB Output is correct
3 Correct 2 ms 15964 KB Output is correct
4 Correct 2 ms 15800 KB Output is correct
5 Correct 2 ms 15964 KB Output is correct
6 Correct 2 ms 15964 KB Output is correct
7 Correct 2 ms 15964 KB Output is correct
8 Correct 2 ms 15964 KB Output is correct
9 Correct 3 ms 15964 KB Output is correct
10 Correct 2 ms 15756 KB Output is correct
11 Correct 2 ms 15964 KB Output is correct
12 Correct 2 ms 15780 KB Output is correct
13 Correct 2 ms 15964 KB Output is correct
14 Correct 2 ms 15960 KB Output is correct
15 Correct 3 ms 15960 KB Output is correct
16 Correct 3 ms 15960 KB Output is correct
17 Correct 3 ms 15960 KB Output is correct
18 Correct 2 ms 15960 KB Output is correct
19 Correct 2 ms 15984 KB Output is correct
20 Correct 2 ms 15964 KB Output is correct
21 Correct 2 ms 15964 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 15964 KB Output is correct
2 Correct 2 ms 15964 KB Output is correct
3 Correct 2 ms 15964 KB Output is correct
4 Correct 2 ms 15800 KB Output is correct
5 Correct 2 ms 15964 KB Output is correct
6 Correct 2 ms 15964 KB Output is correct
7 Correct 2 ms 15964 KB Output is correct
8 Correct 2 ms 15964 KB Output is correct
9 Correct 3 ms 15964 KB Output is correct
10 Correct 2 ms 15756 KB Output is correct
11 Correct 2 ms 15964 KB Output is correct
12 Correct 2 ms 15780 KB Output is correct
13 Correct 2 ms 15964 KB Output is correct
14 Correct 2 ms 15960 KB Output is correct
15 Correct 3 ms 15960 KB Output is correct
16 Correct 3 ms 15960 KB Output is correct
17 Correct 3 ms 15960 KB Output is correct
18 Correct 2 ms 15960 KB Output is correct
19 Correct 2 ms 15984 KB Output is correct
20 Correct 2 ms 15964 KB Output is correct
21 Correct 2 ms 15964 KB Output is correct
22 Correct 5 ms 15964 KB Output is correct
23 Correct 4 ms 15964 KB Output is correct
24 Correct 5 ms 15964 KB Output is correct
25 Correct 4 ms 15964 KB Output is correct
26 Correct 5 ms 16080 KB Output is correct
27 Correct 5 ms 15960 KB Output is correct
28 Correct 5 ms 15964 KB Output is correct
29 Correct 4 ms 15964 KB Output is correct
30 Correct 4 ms 16172 KB Output is correct
31 Correct 4 ms 15964 KB Output is correct
32 Correct 5 ms 16220 KB Output is correct
33 Correct 5 ms 16220 KB Output is correct
34 Correct 3 ms 15964 KB Output is correct
35 Correct 4 ms 15992 KB Output is correct
36 Correct 4 ms 16052 KB Output is correct
37 Correct 3 ms 15964 KB Output is correct
38 Correct 4 ms 16220 KB Output is correct

Subtask #3
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 15964 KB Output is correct
2 Correct 2 ms 15964 KB Output is correct
3 Correct 2 ms 15964 KB Output is correct
4 Correct 2 ms 15800 KB Output is correct
5 Correct 2 ms 15964 KB Output is correct
6 Correct 2 ms 15964 KB Output is correct
7 Correct 2 ms 15964 KB Output is correct
8 Correct 2 ms 15964 KB Output is correct
9 Correct 3 ms 15964 KB Output is correct
10 Correct 2 ms 15756 KB Output is correct
11 Correct 2 ms 15964 KB Output is correct
12 Correct 2 ms 15780 KB Output is correct
13 Correct 2 ms 15964 KB Output is correct
14 Correct 2 ms 15960 KB Output is correct
15 Correct 3 ms 15960 KB Output is correct
16 Correct 3 ms 15960 KB Output is correct
17 Correct 3 ms 15960 KB Output is correct
18 Correct 2 ms 15960 KB Output is correct
19 Correct 2 ms 15984 KB Output is correct
20 Correct 2 ms 15964 KB Output is correct
21 Correct 2 ms 15964 KB Output is correct
22 Correct 5 ms 15964 KB Output is correct
23 Correct 4 ms 15964 KB Output is correct
24 Correct 5 ms 15964 KB Output is correct
25 Correct 4 ms 15964 KB Output is correct
26 Correct 5 ms 16080 KB Output is correct
27 Correct 5 ms 15960 KB Output is correct
28 Correct 5 ms 15964 KB Output is correct
29 Correct 4 ms 15964 KB Output is correct
30 Correct 4 ms 16172 KB Output is correct
31 Correct 4 ms 15964 KB Output is correct
32 Correct 5 ms 16220 KB Output is correct
33 Correct 5 ms 16220 KB Output is correct
34 Correct 3 ms 15964 KB Output is correct
35 Correct 4 ms 15992 KB Output is correct
36 Correct 4 ms 16052 KB Output is correct
37 Correct 3 ms 15964 KB Output is correct
38 Correct 4 ms 16220 KB Output is correct
39 Correct 239 ms 25172 KB Output is correct
40 Correct 227 ms 25172 KB Output is correct
41 Correct 222 ms 25168 KB Output is correct
42 Correct 213 ms 25408 KB Output is correct
43 Correct 221 ms 25412 KB Output is correct
44 Correct 219 ms 25460 KB Output is correct
45 Correct 441 ms 30212 KB Output is correct
46 Correct 388 ms 34424 KB Output is correct
47 Correct 65 ms 25800 KB Output is correct
48 Correct 51 ms 25796 KB Output is correct
49 Correct 248 ms 25940 KB Output is correct
50 Correct 70 ms 26056 KB Output is correct
51 Correct 217 ms 33388 KB Output is correct