oj.uz

Submission #623345

# Submission time Handle Problem Language Result Execution time Memory
623345 2022-08-05T13:24:32 Z errorgorn Meetings 2 (JOI21_meetings2) C++17
100 / 100
 631 ms 120964 KB 
//もう布団の中から出たくない
//布団の外は寒すぎるから
//布団の中から出たくない
//布団の中はあたたかすぎるから

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int INF=1e18;

struct dat{
	int a=-INF,b=-INF,c=-INF;
	int ab=-INF,bc=-INF;
	int abc=-INF;
	
	dat(){}
	dat(int v){
		a=v,b=-2*v,c=v;
		ab=-v,bc=-v;
		abc=0;
	}
};

dat merge(dat i,dat j){
	dat res;
	res.a=max(i.a,j.a);
	res.b=max(i.b,j.b);
	res.c=max(i.c,j.c);
	res.ab=max({i.ab,j.ab,i.a+j.b});
	res.bc=max({i.bc,j.bc,i.b+j.c});
	res.abc=max({i.abc,j.abc,i.ab+j.c,i.a+j.bc});
	return res;
}

struct node{
	int s,e,m;
	dat val;
	node *l,*r;
	
	node (int _s,int _e){
		s=_s,e=_e,m=s+e>>1;
		
		if (s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void update(int i,int k){
		if (s==e) val=dat(k);
		else{
			if (i<=m) l->update(i,k);
			else r->update(i,k);
			val=merge(l->val,r->val);
		}
	}
} *root=new node(0,400005);

int n;
vector<int> al[200005];
int d[200005];
int ss[200005];
int small[200005];
vector<int> pos[200005];
int IDX=1;

void dfs(int i,int p){
	ss[i]=1;
	small[i]=1e9;
	pos[i].pub(IDX++);
	
	for (auto it:al[i]){
		if (it==p) continue;
		
		d[it]=d[i]+1;
		dfs(it,i);
		ss[i]+=ss[it];
		small[i]=min(small[i],n-ss[it]);
		pos[i].pub(IDX++);
	}
	small[i]=min(small[i],ss[i]);
}

int ans[200005];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin.exceptions(ios::badbit | ios::failbit);
	
	cin>>n;
	
	int a,b;
	rep(x,1,n){
		cin>>a>>b;
		al[a].pub(b);
		al[b].pub(a);
	}
	
	dfs(1,-1);
	
	//rep(x,1,n+1) cout<<small[x]<<" "; cout<<endl;
	
	vector<int> idx;
	rep(x,1,n+1) idx.pub(x);
	sort(all(idx),[](int i,int j){
		return small[i]<small[j];
	});
	
	rep(x,1,n+1) ans[x]=1;
	rep(x,n/2+1,1){
		while (!idx.empty() && x<=small[idx.back()]){
			int u=idx.back(); idx.pob();
			for (auto it:pos[u]) root->update(it,d[u]);
		}
		
		ans[2*x]=root->val.abc+1;
	}
	rep(x,1,n+1) cout<<ans[x]<<endl;
}

Compilation message

meetings2.cpp: In constructor 'node::node(long long int, long long int)':
meetings2.cpp:63:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |   s=_s,e=_e,m=s+e>>1;
      |               ~^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 84820 KB Output is correct
2 Correct 52 ms 84824 KB Output is correct
3 Correct 51 ms 84816 KB Output is correct
4 Correct 50 ms 84796 KB Output is correct
5 Correct 50 ms 84816 KB Output is correct
6 Correct 58 ms 84828 KB Output is correct
7 Correct 58 ms 84812 KB Output is correct
8 Correct 51 ms 84864 KB Output is correct
9 Correct 55 ms 84932 KB Output is correct
10 Correct 57 ms 84816 KB Output is correct
11 Correct 68 ms 84792 KB Output is correct
12 Correct 53 ms 84776 KB Output is correct
13 Correct 67 ms 84812 KB Output is correct
14 Correct 61 ms 84812 KB Output is correct
15 Correct 65 ms 84872 KB Output is correct
16 Correct 47 ms 84808 KB Output is correct
17 Correct 49 ms 84796 KB Output is correct
18 Correct 57 ms 84832 KB Output is correct
19 Correct 49 ms 84864 KB Output is correct
20 Correct 63 ms 84824 KB Output is correct
21 Correct 49 ms 84772 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 84820 KB Output is correct
2 Correct 52 ms 84824 KB Output is correct
3 Correct 51 ms 84816 KB Output is correct
4 Correct 50 ms 84796 KB Output is correct
5 Correct 50 ms 84816 KB Output is correct
6 Correct 58 ms 84828 KB Output is correct
7 Correct 58 ms 84812 KB Output is correct
8 Correct 51 ms 84864 KB Output is correct
9 Correct 55 ms 84932 KB Output is correct
10 Correct 57 ms 84816 KB Output is correct
11 Correct 68 ms 84792 KB Output is correct
12 Correct 53 ms 84776 KB Output is correct
13 Correct 67 ms 84812 KB Output is correct
14 Correct 61 ms 84812 KB Output is correct
15 Correct 65 ms 84872 KB Output is correct
16 Correct 47 ms 84808 KB Output is correct
17 Correct 49 ms 84796 KB Output is correct
18 Correct 57 ms 84832 KB Output is correct
19 Correct 49 ms 84864 KB Output is correct
20 Correct 63 ms 84824 KB Output is correct
21 Correct 49 ms 84772 KB Output is correct
22 Correct 55 ms 85316 KB Output is correct
23 Correct 58 ms 85304 KB Output is correct
24 Correct 57 ms 85412 KB Output is correct
25 Correct 55 ms 85320 KB Output is correct
26 Correct 57 ms 85376 KB Output is correct
27 Correct 56 ms 85384 KB Output is correct
28 Correct 56 ms 85376 KB Output is correct
29 Correct 66 ms 85372 KB Output is correct
30 Correct 61 ms 85460 KB Output is correct
31 Correct 64 ms 85356 KB Output is correct
32 Correct 54 ms 85528 KB Output is correct
33 Correct 60 ms 85636 KB Output is correct
34 Correct 56 ms 85412 KB Output is correct
35 Correct 54 ms 85400 KB Output is correct
36 Correct 55 ms 85432 KB Output is correct
37 Correct 73 ms 85352 KB Output is correct
38 Correct 67 ms 85448 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 84820 KB Output is correct
2 Correct 52 ms 84824 KB Output is correct
3 Correct 51 ms 84816 KB Output is correct
4 Correct 50 ms 84796 KB Output is correct
5 Correct 50 ms 84816 KB Output is correct
6 Correct 58 ms 84828 KB Output is correct
7 Correct 58 ms 84812 KB Output is correct
8 Correct 51 ms 84864 KB Output is correct
9 Correct 55 ms 84932 KB Output is correct
10 Correct 57 ms 84816 KB Output is correct
11 Correct 68 ms 84792 KB Output is correct
12 Correct 53 ms 84776 KB Output is correct
13 Correct 67 ms 84812 KB Output is correct
14 Correct 61 ms 84812 KB Output is correct
15 Correct 65 ms 84872 KB Output is correct
16 Correct 47 ms 84808 KB Output is correct
17 Correct 49 ms 84796 KB Output is correct
18 Correct 57 ms 84832 KB Output is correct
19 Correct 49 ms 84864 KB Output is correct
20 Correct 63 ms 84824 KB Output is correct
21 Correct 49 ms 84772 KB Output is correct
22 Correct 55 ms 85316 KB Output is correct
23 Correct 58 ms 85304 KB Output is correct
24 Correct 57 ms 85412 KB Output is correct
25 Correct 55 ms 85320 KB Output is correct
26 Correct 57 ms 85376 KB Output is correct
27 Correct 56 ms 85384 KB Output is correct
28 Correct 56 ms 85376 KB Output is correct
29 Correct 66 ms 85372 KB Output is correct
30 Correct 61 ms 85460 KB Output is correct
31 Correct 64 ms 85356 KB Output is correct
32 Correct 54 ms 85528 KB Output is correct
33 Correct 60 ms 85636 KB Output is correct
34 Correct 56 ms 85412 KB Output is correct
35 Correct 54 ms 85400 KB Output is correct
36 Correct 55 ms 85432 KB Output is correct
37 Correct 73 ms 85352 KB Output is correct
38 Correct 67 ms 85448 KB Output is correct
39 Correct 631 ms 110228 KB Output is correct
40 Correct 614 ms 109636 KB Output is correct
41 Correct 593 ms 110280 KB Output is correct
42 Correct 596 ms 110756 KB Output is correct
43 Correct 585 ms 110648 KB Output is correct
44 Correct 620 ms 110680 KB Output is correct
45 Correct 556 ms 116980 KB Output is correct
46 Correct 479 ms 120964 KB Output is correct
47 Correct 566 ms 110712 KB Output is correct
48 Correct 526 ms 111288 KB Output is correct
49 Correct 582 ms 110868 KB Output is correct
50 Correct 524 ms 111424 KB Output is correct
51 Correct 451 ms 120572 KB Output is correct