Submission #921248

#	Time	Username	Problem	Language	Result	Execution time	Memory
921248		KiaRez	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	7 ms	33372 KiB

meetings2

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 3e5+23, lg = 18;
ll Mod = 1e9+7; //998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

int n, h[N], subt[N], ans[N], seg[5][2*N], par[lg][N];
vector<int> adj[N];

void update(int ind, int val, int id) {
	if(ind == 0) return;
	if(ind >= (1<<lg)) {
		if(val==-1) seg[id][ind] = 0;
		seg[id][ind] = max(seg[id][ind], val);
	} else {
		seg[id][ind] = max(seg[id][2*ind], seg[id][2*ind+1]);
	}
	update(ind/2, val, id);
}

int query(int l, int r, int id, int ind=1, int lc=1, int rc=(1<<lg)+1) {
	if(lc>=r || l>=rc) return -n;
	if(lc>=l && rc<=r) return seg[id][ind];
	int mid = (lc+rc)/2;
	int res = max(query(l, r, id, 2*ind, lc, mid), query(l, r, id, 2*ind+1, mid, rc));
	if(res == 0) return -n;
	return res;
}

void init(int v, int p=0) {
	subt[v] = 1, h[v] = h[p] + 1, par[0][v] = p;
	for(int i=1; i<lg; i++) par[i][v] = par[i-1][par[i-1][v]];
	for(int u : adj[v]) {
		if(u == p) continue;
		init(u, v); subt[v] += subt[u];
	}
}

void add(int v, int p, int id) {
	update(subt[v]+(1<<lg)-1, h[v], id);
	for(int u : adj[v]) {
		if(u == p) continue;
		add(u, v, id);
	}
}

void clen(int v, int p, int id) {
	update(subt[v]+(1<<lg)-1, -1, id);
	for(int u : adj[v]) {
		if(u == p) continue;
		clen(u, v, id);
	}
}

void dfs(int v, int p=0) {
	int mx = 0;
	for(int u : adj[v]) {
		if(u == p) continue;
		mx = (subt[mx] > subt[u] ? mx : u);
	}
	for(int u : adj[v]) {
		if(u == p || u == mx) continue;
		dfs(u, v);
		clen(u, v, 1);
	}
	for(int u : adj[v]) {
		if(u == p || u == mx) continue;
		add(u, v, 3);
		for(int i=1; i<=subt[u]; i++) {
			ans[2*i] = max(ans[2*i], query(i, n+1, 3)+query(i, n+1, 2)+1-2*h[v]);
		}
		clen(u, v, 3);
		add(u, v, 2);
	}
	for(int u : adj[v]) {
		if(u == p || u == mx) continue;
		clen(u, v, 2);
	}
	reverse(all(adj[v]));
	for(int u : adj[v]) {
		if(u == p || u == mx) continue;
		add(u, v, 3);
		int x = n-subt[u];
		ans[2*x] = max(ans[2*x], query(x, n+1, 3)-h[v]+1);
		for(int i=1; i<=subt[u]; i++) {
			ans[2*i] = max(ans[2*i], query(i, n+1, 3)+query(i, n+1, 2)+1-2*h[v]);
		}
		clen(u, v, 3);
		add(u, v, 2);
	}
	reverse(all(adj[v]));
	if(mx > 0) dfs(mx, v);

	for(int i=1; i<=subt[v]-subt[mx]; i++) {
		ans[2*i] = max(ans[2*i], query(i, n+1, 1)+query(i, n+1, 2)+1-2*h[v]);
	}
	int x = n-subt[mx];
	ans[2*x] = max(ans[2*x], query(x, n+1, 1)-h[v]+1);
	int w = v;
	for(int i=lg-1; i>=0; i--) {
		if(par[i][w]<=1) continue;
		int ff = par[i][w];
		if(subt[par[0][ff]] - subt[ff] >= subt[v]) {
			w = ff;
		}
	}
	if(subt[par[0][w]] - subt[w] >= subt[v]) {
		ans[2*subt[v]] = max(ans[2*subt[v]], h[v]-h[w]+2);
	}

	// add to seg1
	for(int u : adj[v]) {
		if(u == p || u == mx) continue;
		add(u, v, 1);
		clen(u, v, 2);
	}
	update(subt[v]+(1<<lg)-1, h[v], 1);
}

int main () {
	ios_base::sync_with_stdio(false), cin.tie(0);

	cin>>n;
	for(int v,u,i=1; i<n; i++) {
		cin>>v>>u; adj[v].pb(u); adj[u].pb(v);
	}
	init(1);
	dfs(1);

	for(int i=n; i>=1; i--) {
		ans[i] = max(ans[i+1], ans[i]);
	}
	for(int i=1; i<=n; i++) {
		if(i%2 == 1) cout<<1<<endl;
		else cout<<max(1, ans[i])<<endl;
	}

	return 0;
}

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