제출 #1170223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170223		monkey133	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	445 ms	72420 KiB

meetings2

#include <bits/stdc++.h>
//#include "includeall.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i) 
#define RFOR(i, x, n) for (ll i =x; i>=n; --i) 
#pragma GCC optimize("O3","unroll-loops")
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<pi, pi> piii;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll n;
vector<ll> adj[200005];
ll twok[200005][25], dist[200005], siz[200005], ans[200005];
vector<ll> sub[200005];


ll find_centroid(ll p = -1, ll from = 1)
{
	for (ll u: adj[from])
	{
		if (u==p) continue;
		if (siz[u]>n/2) return find_centroid(from, u);
	}
	return from;
}

void predfs(ll x = 1, ll p = -1)
{
	siz[x] = 1;
	for (ll u : adj[x]) if (p!=u)
	{
		predfs(u, x);
		siz[x] += siz[u];
	}
}

void dfs(ll x = 1, ll p = -1)
{
	for (ll k=1; k<20; ++k)
	{
		if (twok[x][k-1]!=-1) twok[x][k] = twok[twok[x][k-1]][k-1];
		else twok[x][k] = -1;
	}
	siz[x] = 1;
	for (ll u: adj[x])if (p!=u)
	{
		dist[u] = dist[x] + 1;
		twok[u][0] = x;
		dfs(u, x);
		siz[x] += siz[u];
	}
	sub[siz[x]].pb(x);
}

ll lca(ll a, ll b)
{
	if (a==b) return a;
	if (dist[a] < dist[b]) swap(a, b);
	for (ll k=0; k < 20; ++k) if ((1LL << k)&(dist[a] - dist[b])) a = twok[a][k];
	if (a==b) return a;
	for (ll k=19; k>=0; --k) if (twok[a][k]!=twok[b][k]) a= twok[a][k], b = twok[b][k];
	return twok[a][0];
}

ll sp(ll a, ll b) {return dist[a] + dist[b] - 2*dist[lca(a, b)];}

int main()
{
	cin >> n;
	for (ll i=0; i<n-1; ++i)
	{
		ll a, b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	predfs();
	ll root = find_centroid();
	//show(root);
	twok[root][0] = -1;
	dist[root] = 0;
	dfs(root);
	ll l = root, r = root, d = 0;
	for (ll i=n/2; i>=1; --i)
	{
		for (ll u: sub[i])
		{
			//show(u);
			ll d1 = sp(l, u), d2= sp(r, u);
			//show2(d1, d2);
			if (d2 > d1) {swap(d2, d1); swap(l, r);}
			if (d < d1) {r = u, d = sp(l, r);}
		}
		ans[i] = d;
	}
	for (ll i=1; i<=n; ++i) cout << ((i%2)?1:ans[i/2] + 1) << endl;
}

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