Submission #408459

#	Time	Username	Problem	Language	Result	Execution time	Memory
408459		ryansee	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	502 ms	44612 KiB

meetings2

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

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusive
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

using ll=long long;
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; 

long long LLINF = 1e18;
int INF = 1e9+1e6;
#define MAXN (200006)
int n, p[MAXN][18], dist[MAXN], st[MAXN], en[MAXN], co, sz[MAXN];
vector<int> v[MAXN];
void dfs(int x,int par) {
	st[x] = co++, p[x][0]=par, sz[x] = 1;
	for(auto i:v[x]) if(i^par) dist[i]=dist[x]+1, dfs(i, x), sz[x] += sz[i];
	en[x] = co-1;
}
bool isp(int a,int b) { return st[a]<=st[b]&&en[a]>=en[b]; }
int lca(int x,int y) {
	if(isp(x,y)) return x;
	if(isp(y,x)) return y;
	DEC(i,17,0) if(!isp(p[x][i], y)) x=p[x][i];
	return p[x][0];
}
int disty(int a,int b) { return dist[a]+dist[b]-2*dist[lca(a,b)]; }
int A, B, out[MAXN], c;
void SZ(int x,int p) {
	sz[x] = 1;
	for(auto i:v[x]) if(i^p) SZ(i, x), sz[x] += sz[i];
}
int dfs2(int x,int p) {
	for(auto i:v[x]) if(i^p && sz[i] > n/2) return dfs2(i, x);
	return x;
}
int main() {
	FAST
	cin>>n;
	FOR(i,1,n-1) {
		int a, b;
		cin>>a>>b;
		v[a].eb(b), v[b].eb(a);
	}
	SZ(1, 1);
	c = dfs2(1, 1);
	dfs(c, c);
	FOR(j,1,17) FOR(i,1,n) p[i][j]=p[p[i][j-1]][j-1];
	A=B=-1;
	vector<pi> V;
	int mx = 0;
	for(auto j:v[c]) mx = max(mx, sz[j]);
	sz[c] -= mx;
	FOR(i,1,n) {
		// cerr<<i<<": "<<sz[i]<<'\n';
		V.eb(sz[i], i);
	}
	sort(all(V));
	for(ll i=n/2;i>=1;--i) {
		while(V.size() && V.back().f >= i) {
			int x = V.back().s; V.pop_back();
			if(A==-1) A=B=x;
			else {
				if(disty(x, A) >= disty(A, B) && disty(x, A) >= disty(x, B)) {
					B = x;
				} else if(disty(x, B) >= disty(A, B)) {
					A = x;
				}
			}
		}
		if(A == -1) out[i*2]=0;
		else out[i*2] = disty(A, B);
	}
	FOR(i,1,n) cout<<out[i]+1<<'\n';
}

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