제출 #496244

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
496244		hohohaha	Meetings 2 (JOI21_meetings2)	C++14	4 / 100	21 ms	22836 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]; 

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

int get(int i, int l, int r, int ll, int rr) { 
	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)); 
}

int mx2[maxn << 2]; 

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

int get2(int i, int l, int r, int p) { 
	if(p > r or l > p) return -inf; 
	int re = -inf; 
	if(l <= p and p <= r) {
		re = mx2[i]; 
	}
	if(l < r) {
		int mi = l + r >> 1;
		re = max({re, get2(i << 1, l,mi, p), get2(i << 1 | 1, mi + 1, r, p)}); 
	}
	return re; 
}

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; 
}

ii dp[maxn][2]; 

void prep(int i, int p) { 
	sz[i] = 1; 
	dep[i] = i == p? 0: 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 mydep = dep[i]; // one is ancestor of another
	
	int mx = mydep; 
	
	while(1) { 
		// prep for on off
		
		update2(1, 1, n, in[head[i]], in[i] - 1, mydep); // max that comes from heavy child
	
		// off on
		
		mx = max(mx, get(1,1, n, in[head[i]], in[i] - 1) + mydep); 
		
		// JUMP
		
		if(head[i] == par[head[i]]) return mx; 
		int temp = head[i]; 
		i = par[head[i]];
		
		// off, off
		
		if(dp[i][0].se == temp) dp[i][0] = {mydep, temp}; 
		else if(dp[i][1].se == temp) dp[i][1] = {mydep, temp}; 
		else if(dp[i][1].fi < mydep) dp[i][1] = {mydep, temp}; 
		if(dp[i][0] < dp[i][1]) swap(dp[i][0], dp[i][1]); 
		mx = max(mx, dp[i][0].fi + dp[i][1].fi - 2 * dep[i]); 
		
		// on  off
		mx = max(mx, mydep + get2(1, 1, n, in[i]) - 2 * dep[i]);
		
		// prep for off on 
		
		update(1, 1, n, in[i], mydep - 2 * dep[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;
	
	fill(all(mx), -inf); 
	fill(all(mx2), -inf); 
	fori(i,1,n) dp[i][0] = dp[i][1] = ii(-inf, -inf); 

	fori(i,1,n) { 
		ev[sz[i]].eb(i); 
	}
	
	ford(i, n, 1) { 
		if(i & 1) { 
		}
		else { 
			ans[i] = ans[i + 2]; 
			for(auto id: ev[i / 2]) { 
			
//				cout << id << sp << climb(id) << sp << climb(id) + dep[id] << endl;
				ans[i] = max(ans[i], climb(id)); 
			}
		}
	}
	
	fori(i,1,n) { 
		cout << ans[i] + 1 << endl; 
	}
			
}

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

meetings2.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
meetings2.cpp:85:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |   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:95:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |  int mi  = l + r >> 1;
      |            ~~^~~
meetings2.cpp: In function 'void update2(long long int, long long int, long long int, long long int, long long int, long long int)':
meetings2.cpp:107:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  107 |   int mi = l + r >> 1;
      |            ~~^~~
meetings2.cpp: In function 'long long int get2(long long int, long long int, long long int, long long int)':
meetings2.cpp:120:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  120 |   int mi = l + r >> 1;
      |            ~~^~~

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