Submission #1216719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216719		salmon	Meetings 2 (JOI21_meetings2)	C++20	0 / 100	3 ms	4932 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] = -1;
	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(parent[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);

	if(sise[i] <= 2) return;
	
	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<int> v = {N};
	
	for(int j : adjlst[c]){
		if(used[j]) continue;
		
		vector<int> temp = {N};
		
		loadfs(j,c,1,temp);
		
		for(int i = 0; i < temp.size(); i++){
			int it = upper_bound(v.begin(),v.end(),temp[i],greater<int>()) - v.begin() - 1;
			
			suff[it + i] = max(suff[it + i],temp[i]);
			
			if(temp[i] >= v.back()){
				auto it = lower_bound(v.begin(), v.end(), temp[i], greater<int>());
				suff[(it - v.begin()) + i] = max(suff[(it - v.begin()) + i],*it);
			}
		}
		
		if(temp.size() > v.size()) swap(temp,v);
		
		for(int i = 0; i < temp.size(); i++){
			v[i] = max(v[i],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;
	}
	
	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);
		}
	}
}

Compilation message (stderr)

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

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