Submission #1216830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216830		salmon	Meetings 2 (JOI21_meetings2)	C++20	0 / 100	2 ms	4940 KiB

meetings2

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

int N;
vector<int> adjlst[200100];
int u,v;
int suff[200100];
bool used[200100];
int tparent[200100];
int tsise[200100];
int sise[200100];
int parent[200100];
int d[200100];

void tfs(int i, int p){
	tparent[i] = p;
	tsise[i] = 1;
	
	for(int j : adjlst[i]){
		if(j == p) continue;
		tfs(j,i);
		
		tsise[i] += tsise[j];
	}
}

void dfs(int i, int p){
	sise[i] = 1;
	parent[i] = p;
	
	for(int j : adjlst[i]){
		if(j == p || used[j]) continue;
		dfs(j,i);
		
		sise[i] += sise[j];
	}
}

void loadfs(int i, int p, int de, vector<int> &a){
	if(de == a.size()){
		a.push_back(0);
	}
	
	for(int j : adjlst[i]){
		if(j == p || used[j]) continue;
		loadfs(j,i, de + 1, a);
	}
	
	if(tparent[i] == p){
		a[de] = max(a[de], tsise[i]);
	}
	else{
		a[de] = max(a[de],N - tsise[p]);
	}
}

void solve(int i){
	
	int c = i;
	
	dfs(i,-1);
	
	while(true){
		bool die = true;
		
		for(int j : adjlst[c]){
			if(j == parent[c] || used[j]) continue;
			if(sise[j] * 2 >= sise[i]){
				c = j;
				die = false;
				break;
			}
		}
		
		if(die) break;
	}
	
	used[c] = true;
	
	vector<pair<int,int>> v = {{N,N}};
	vector<int> pros;
	
	for(int j : adjlst[c]){
		if(used[j]) continue;
		
		int num;
		
		if(tparent[j] == c){
			num = N - tsise[j];
		}
		else{
			num = tsise[c];
		}
		
		vector<int> temp = {N};
		loadfs(j,c,1,temp);
		
		for(int i = 1; i < temp.size(); i++){
			if(v.size() == i) v.push_back({0,0}); 
			v[i] = max(max(v[i],{temp[i],v[i].first}), {v[i].first,temp[i]});
			suff[i] = max(suff[i], min(temp[i], num) );
		}
	}
	
	for(pair<int,int> ii : v) pros.push_back(ii.first);
	
	for(int j : adjlst[c]){
		if(used[j]) continue;
		
		vector<int> temp = {N};
		loadfs(j,c,1,temp);
		
		for(int i = 1; i < temp.size(); i++){
			if(v[i].first == temp[i]){
				if(v[i].second == 0) pros.pop_back();
			}
			else{
				pros[i] = v[i].second;
			}
		}
		
		if(!pros.empty()){		
			for(int i = 1; i < temp.size(); i++){
				if(pros[0] >= temp[i]){
					auto it = upper_bound(pros.begin(),pros.end(),temp[i],greater<int>());
					suff[i + (it - pros.begin() - 1)] = max(suff[i + (it - pros.begin() - 1)], temp[i]);
				}
			}
		}
	}
	
	/*printf("%d\n",c);
	for(int i = 0; i <= N; i++){
		printf("%d ",suff[i]);
	}
	printf("\n");*/
	
	for(int j : adjlst[c]){
		if(!used[j]) solve(j);
	}
}

int main(){
	
	scanf(" %d",&N);
	
	for(int i = 0; i < N - 1; i++){
		scanf(" %d",&u);
		scanf(" %d",&v);
		
		adjlst[u].push_back(v);
		adjlst[v].push_back(u);
	}
	
	for(int i = 0; i <= N; i++){
		suff[i] = 0;
		used[i] = false;
	}
	
	suff[0] = N;
	
	tfs(1,-1);
	solve(1);
	
	for(int i = N - 1; i >= 0; i--){
		suff[i] = max(suff[i + 1],suff[i]);
	}

	int it = N;

	for(int i = 1; i <= N; i++){
		if(i % 2 == 1){
			printf("1\n");
		}
		else{
			while(suff[it] < i/2) it--;
			
			printf("%d\n",it + 1);
		}
	}
}
/*
4
1 2
3 2
4 3

7
1 2
2 3
3 4
4 5
2 6
3 7

6
1 2
2 3
2 4
4 5
4 6
 */

Compilation message (stderr)

meetings2.cpp: In function 'int main()':
meetings2.cpp:145:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
meetings2.cpp:148:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |                 scanf(" %d",&u);
      |                 ~~~~~^~~~~~~~~~
meetings2.cpp:149:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |                 scanf(" %d",&v);
      |                 ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 16
• Subtask 3: 0 / 80