제출 #544618

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
544618		ivan_tudor	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	532 ms	72404 KiB

meetings2

#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
vector<int> gr[N];
set<int> auxgr[N];
struct helpertime{
	int nod, dad;
	int sz;
};
int sz[N];
priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> leafs;
vector<helpertime> ht;
int ans[N];


int par[20][N];
int in[N], out[N];
int h[N];
void dfs_prec(int nod, int dad, int &cnt){
	h[nod] = h[dad] + 1;
	in[nod] = ++cnt;
	par[0][nod] = dad;
	for(int i = 1; i < 20; i ++)
		par[i][nod] = par[i - 1][par[i - 1][nod]];
	for(auto x:gr[nod]){
		if(x == dad)
			continue;
		dfs_prec(x, nod, cnt);
	}
	out[nod] = cnt;
}
bool is_dad(int dad, int son){
	if(in[dad] <= in[son] && out[son] <= out[dad])
		return true;
	return false;
}
int get_dist(int a, int b){
	if(h[a] > h[b])
		swap(a, b);
	if(is_dad(a, b))
		return h[b] - h[a] + 1;
	int lca = a;
	for(int p2 = 19; p2>=0; p2--){
		int up = par[p2][lca];
		if(up != 0 && is_dad(up, b) == false)
			lca = up;
	}
	lca = par[0][lca];
	return h[a] - h[lca] + 1 + h[b] - h[lca];
}

int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n;
  cin>>n;
  for(int i = 1; i<n; i++){
		int x, y;
		cin>>x>>y;
		gr[x].push_back(y);
		gr[y].push_back(x);

		auxgr[x].insert(y);
		auxgr[y].insert(x);
  }
	for(int i = 1; i<=n; i++){
		sz[i] = 1;
	}
	for(int i = 1; i<=n; i++){
		if(auxgr[i].size() == 1){
			leafs.push({sz[i], i});
		}
	}

	for(int t = 2; t <= n/2 + 1; t++){
		while(leafs.size() && leafs.top().first < t){
			int nod = leafs.top().second;
			leafs.pop();
			if(auxgr[nod].size()){
				assert(auxgr[nod].size() == 1);
				int vec = *auxgr[nod].begin();
				auxgr[nod].erase(vec);
				auxgr[vec].erase(nod);
				sz[vec] += sz[nod];
				ht.push_back({nod, vec, sz[nod]});
				if(auxgr[vec].size() == 1){
					leafs.push({sz[vec], vec});
				}
			}
		}
	}
	int cnt = 0;
	dfs_prec(1, 0, cnt);

	int root = 0;
	for(int i = 1; i<=n; i++)
		if(sz[i] == n)
			root = i;
	int diama = root, diamb = root;
	int dst = 1;
	for(int t = n/2; t>=1; t--){
		while(ht.size() && ht.back().sz >= t){
			int newnod = ht.back().nod;
			int dstna = get_dist(diama, newnod);
			int dstnb = get_dist(diamb, newnod);
			if(dstna > dst && dstna >= dstnb){
				dst = dstna;
				diamb = newnod;
			}
			else if(dstnb > dst && dstnb >= dstna){
				dst = dstnb;
				diama = newnod;
			}
			ht.pop_back();
		}
		ans[2*t] = dst;
		ans[2*t + 1] = 1;
	}
	ans[1] = 1;
	for(int i = 1; i<=n; i++){
		cout<<ans[i]<<"\n";
	}
  return 0;
}

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