제출 #723493

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
723493		Abrar_Al_Samit	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	1423 ms	29632 KiB

meetings2

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

const int nax = 2e5 + 3;
vector<int>g[nax];
int n;
int sub[nax];
bool r[nax];
vector<pair<int,int>>stk;
int ans[nax];

int dfs(int v, int p = 0) {
	sub[v] = 1;
	for(int u : g[v]) if(u!=p && !r[u]) {
		sub[v] += dfs(u, v);
	}
	return sub[v];
}
int get_centroid(int v, int sz, int p = 0) {
	for(int u : g[v]) if(u!=p && !r[u]) {
		if(sub[u] * 2 > sz) {
			return get_centroid(u, sz, v);
		}
	}
	return v;
} 
void dfs2(int v, int p, int d) {
	stk.emplace_back(sub[v], d);
	for(int u : g[v]) if(u!=p && !r[u]) {
		dfs2(u, v, d+1);
	}
}
void centroid(int v) {
	int C = get_centroid(v, dfs(v));
	dfs(C);

	//do here
	for(int t : {1, 2}) {
		set<pair<int,int>>pr = {{sub[C], 0}};
		for(int u : g[C]) if(!r[u]) {
			stk.clear();
			dfs2(u, C, 1);

			for(auto [sz, d] : stk) {
				// query
				auto it = pr.lower_bound(make_pair(sz, -1));
				if(it!=pr.end()) {
					ans[sz * 2] = max(ans[sz * 2], it->second+d+1);
					//f(C==2) cerr<<sz*2<<' '<<it->second+d+1<<'\n';
				}
			}
			for(auto [sz, d] : stk) {
				// insert

				auto it = pr.lower_bound(make_pair(sz, -1));
				if(it!=pr.end() && it->first>=sz && it->second>=d) continue;
				while(1) {
					it = pr.upper_bound(make_pair(sz, 1e9));
					if(it==pr.begin()) break;
					--it;
					if(it->second<=d) {
						pr.erase(it);
					} else break;
				}
				pr.insert({sz, d});
			}
		}
		reverse(g[C].begin(), g[C].end());
	}

	r[C] = 1;
	for(int u : g[C]) if(!r[u]) {
		centroid(u);
	}
}
void PlayGround() {
	cin>>n;
	for(int i=0; i<n-1; ++i) {
		int u, v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}

	centroid(1);

	int mx = 1;
	for(int i=n; i>0; --i) {
		mx = max(mx, ans[i]);
		ans[i] = mx;
	}
	for(int i=1; i<=n; ++i) {
		if(i&1) cout<<"1\n";
		else cout<<ans[i]<<'\n';
	}

	// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	PlayGround();
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

meetings2.cpp: In function 'void centroid(int)':
meetings2.cpp:38:10: warning: unused variable 't' [-Wunused-variable]
   38 |  for(int t : {1, 2}) {
      |          ^

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