Submission #572821

#	Time	Username	Problem	Language	Result	Execution time	Memory
572821		Arvin	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	8 ms	10116 KiB

meetings2

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int maxN = 2e5 + 5;
const int logN = log2(maxN)+1;

vector<int> adj[maxN];
int parent[logN][maxN], sz[maxN], depth[maxN];
int c[maxN];

void dfs(int curNode, int prvNode, int d = 1){
	parent[0][curNode] = prvNode;
	for(int x=1;x<logN;x++){
		parent[x][curNode] = parent[x-1][parent[x-1][curNode]];
	}
	sz[curNode] = 1;
	c[curNode] = 0;
	depth[curNode] = d;
	for(auto nxt : adj[curNode]){
		if(nxt != prvNode){
			dfs(nxt, curNode, d+1);
		}
	}
}

void dfs2(int curNode, int prvNode){
	for(auto nxt : adj[curNode]){
		if(nxt != prvNode){
			dfs2(nxt, curNode);
			c[curNode] += (c[nxt] != 0);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	
	int n;
	cin >> n;
	
	for(int x=0;x<n-1;x++){
		int a, b;
		cin >> a >> b;
		
		a--; b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	dfs(0, 0);
	
	pair<int, int> mx = {-1, -1};
	for(int x=0;x<n;x++){
		mx = max(mx, {depth[x], x});
	}
	
	dfs(mx.second, mx.second);
	
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	multiset<int> st;
	int cnt[n];
	int d[n];
	fill(d, d+n, 0);
	fill(cnt, cnt+n, 0);
	fill(c, c+n, 0);
	
	for(int x=0;x<n;x++){
		if(adj[x].size() == 1){
			pq.push({1, x});
			st.insert(1);
			c[x] = 1;
			sz[x] = 1;
			cnt[x] = 1;
			d[x] = min(mx.first-depth[x]+1, depth[x]);
		}
	}
	
	dfs2(mx.second, mx.second);
	
	for(int x=0;x<n;x++){
		if(depth[x] != 1){
			c[x]++;
		}
	}
	
	for(int x=1;x<=n;x++){
		if(x&1){
			cout << "1\n";
		} else {
			while(!pq.empty() && pq.top().first < x/2){
				int curNode = pq.top().second;
				st.erase(st.find(d[curNode]));
				pq.pop();
				
//				cout << "- " << curNode << "\n";
				int par = -1;
				for(auto nxt : adj[curNode]){
//					cout << nxt << " = " << cnt[nxt] << " " << c[nxt] << "\n";
					if(cnt[nxt]+1 < c[nxt]){
						par = nxt;
						break;
					}
				}
				
				if(par == -1) continue;
				
				cnt[par]++;
				if(cnt[par]+1 == c[par]){
					sz[par] = 1;
					for(auto nxt : adj[par]){
//						cout << "nxt is " << nxt << " -> " << cnt[nxt] << " " << c[nxt] << " " << sz[nxt] << "\n";
						if(cnt[nxt]+1 == c[nxt]){
							sz[par] += sz[nxt];
						}
					}
//					cout << "+ " << par << " " << sz[par] << "\n";
					pq.push({sz[par], par});
					d[par] = d[curNode]+1;
					st.insert(d[par]);
				}
			}
			
			int mn1 = -1, mn2 = -1;
			for(auto val : st){
//				cout << " = " << val << "\n";
				if(mn1 == -1){
					mn1 = val;
				} else if(mn2 == -1){
					mn2 = val;
				} else {
					break;
				}
			}
			
			assert(mn1 != -1 && mn2 != -1);
			cout << mx.first-mn1-mn2+2 << "\n";
		}
	}
//	cout << diameter << " --\n";
    return 0;
}

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