제출 #496202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
496202		hohohaha	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	5 ms	9716 KiB

meetings2

// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")

#include "bits/stdc++.h"
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int> 
#define vvi vector<vi>


#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front

#define fr front
#define bc back

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)

#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '

#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

void solve();

signed main() {
// freopen("input.inp","r",stdin);
// freopen("output.out","w",stdout);
//   fastio();
   int tc = 1;
   fori(test, 1, tc) {
      solve();
   }
   return 0;
}

#define int long long
const ld pi = 4 * atan(1.0), eps = 1e-9;

const int maxn = 2e5 + 5, inf = LLONG_MAX / 10ll;

int n; 

vi g[maxn]; 

int sz[maxn]; 

int cen; 

int dep[maxn], hv[maxn], head[maxn], par[maxn]; int in[maxn], inptr, id[maxn]; 

int mx[maxn << 2], base[maxn << 2]; 

int lz[maxn << 2];

void build(int i, int l, int r) { 
	if(l == r) { 
		base[i] = -2 * dep[id[l]];
		mx[i] = -inf; 
	}
	else { 
		int mi = l + r >> 1; 
		build(i << 1, l, mi); 
		build(i << 1 | 1, mi + 1, r); 
		
		base[i] = max(base[i << 1], base[i << 1 | 1]); 
		mx[i] = -inf; 
	}
}

void pd(int i, int l, int r) {
	mx[i] = max(mx[i], base[i] + lz[i]); 
	if(l < r) { 
		lz[i << 1] = max(lz[i << 1], lz[i]); 
		lz[i << 1 | 1] = max(lz[i << 1 | 1], lz[i]); 
	}
}

void update(int i, int l, int r, int ll, int rr, int v) { 
	pd(i, l, r); 
	if(ll > r or  l > rr) return; 
	if(ll <= l and r <= rr) { 
		lz[i] = max(lz[i], v);
		pd(i, l, r); 
	}
	else { 
		int mi = l + r >> 1; 
		update(i << 1, l, mi, ll, rr, v); 
		update(i << 1 | 1, mi + 1, r, ll, rr, v); 
		mx[i] = max(mx[i << 1], mx[i << 1 | 1]); 
	}
}

int get(int i, int l, int r, int ll, int rr) { 
	pd(i, l, r);
	if(ll > r or l > rr) return -inf; 
	if(ll <= l and r <= rr) return mx[i]; 
	int mi  = l + r >> 1; 
	return max(get(i << 1, l, mi, ll, rr), get(i << 1 | 1, mi + 1, r, ll, rr)); 
}

void getsz(int i, int p) { 
	sz[i] = 1; 
	for(int j: g[i]) { 
		if(j - p) { 
			getsz(j, i); 
			sz[i] += sz[j]; 
		}
	}
}

int getcen(int i,int p) {
	for(int j: g[i]) { 
		if(j - p) { 
			if(sz[j] * 2 > n) return getcen(j, i); 
		}
	}
	
	return i; 
}

void prep(int i, int p) { 
	sz[i] = 1; 
	dep[i] = dep[p] + 1; 
	par[i] = p; 
	
	for(int j: g[i]) { 
		if(j - p) {
			prep(j, i); 
			sz[i] += sz[j]; 
			if(!hv[i] or sz[j] > sz[hv[i]]) hv[i] = j; 
		}
	}
}

void hld(int i, int p) { 
	in[i] = ++inptr; id[inptr] = i; head[i] = (i == hv[p]? head[p]: i); 

	if(hv[i]) { 
		hld(hv[i], i); 
	}
	for(int j: g[i]) { 
		if(j - p and j - hv[i]) { 
			hld(j, i); 
		}
	}
}

int climb(int i) { 
	int mx = -inf; 
	
	while(1) { 
//		cout << i << endl;
		mx = max(mx, get(1,1, n, in[head[i]], in[i])); 
		if(head[i] == par[head[i]]) return mx; 
		assert(i); 
		i = par[head[i]];
	}
}

void updatepath(int i, int v) { 
	while(1) { 
//		cout << i << endl;
		update(1,1, n, in[head[i]], in[i], v); 
		if(head[i] == par[head[i]]) return; 
		i = par[head[i]]; 
		assert(i); 
	}
}

vi ev[maxn]; 
int ans[maxn]; 

void solve() {
	cin >> n; 
	
	fori(i,1,n - 1) { 
		int u, v; cin >> u >> v;
		g[u].eb(v); 
		g[v].eb(u); 
	}
	
	getsz(1,1); 
	int root = getcen(1,1); 
	getsz(root, root); 
	
	prep(root, root); 
	hld(root, root); 
	
//	fori(i,1,n) cout << id[i] << sp << par[head[id[i]]] << endl;
	
	build(1,1,n); 
//	
	fori(i,1,n) { 
		ev[sz[i]].eb(i); 
	}
	
	updatepath(root, dep[root]);
	ford(i, n, 1) { 
		if(i & 1) { 
			ans[i] = 1; 
		}
		else { 
			for(auto id: ev[i / 2]) { 
				ans[i] = max({1ll, ans[i + 2], climb(id) + dep[id] + 1}); 
				updatepath(id, dep[id]); 
			}
		}
	}
	
	fori(i,1,n) { 
		cout << ans[i] << endl; 
	}
			
}

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

meetings2.cpp: In function 'void build(long long int, long long int, long long int)':
meetings2.cpp:87:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |   int mi = l + r >> 1;
      |            ~~^~~
meetings2.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, long long int)':
meetings2.cpp:112:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |   int mi = l + r >> 1;
      |            ~~^~~
meetings2.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
meetings2.cpp:123:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |  int mi  = l + r >> 1;
      |            ~~^~~

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