제출 #387329

#제출 시각아이디문제언어결과실행 시간메모리
387329SeDunionEvent Hopping 2 (JOI21_event2)C++17
0 / 100
11 ms9956 KiB
//#pragma GCC target ("avx2") //#pragma GCC optimization ("O3") //#pragma GCC optimization ("unroll-loops") #include <algorithm> #include <iostream> #include <vector> using namespace std; using ll = long long; const int N = 2e5 + 66; const int inf = 1e9; inline void chk(int &a, int b) {a=max(a,b);} vector<int>g[N]; int d[N], sz[N]; int tin[N], tout[N], timer, id[N]; void precalc(int v, int p = 1) { sz[v] = 1; tin[v] = timer++; id[tin[v]] = v; for (int to : g[v]) if (to != p) { d[to] = d[v] + 1; precalc(to, v); sz[v] += sz[to]; } tout[v] = timer; } int D[N], ans[N], cur[N], D2[N]; int n, pq[N]; void dfs(int v, int p = -1, bool cl = 0) { int mx = -1; for (int to : g[v]) if (to != p) if (mx == -1 || sz[mx] < sz[to]) mx = to; for (int to : g[v]) if (to != p && to != mx) dfs(to, v, 1); if (mx != -1) dfs(mx, v, 0); int V = 2 * d[v]; for (int to : g[v]) if (to != p && to != mx) { for (int l = tin[to] ; l < tout[to] ; ++ l) { int a = id[l]; chk(cur[pq[a]], d[a] - V); chk(D2[pq[a]], d[a]); } for (int i = pq[to] ; i >= 1 ; -- i) { chk(ans[i], cur[i] + D[i]); chk(D[i], D2[i]); if (i < sz[to]) chk(D[i], D[i + 1]); chk(cur[i - 1], cur[i]); cur[i] = -inf; } } chk(D[pq[v]], d[v]); for (int i = pq[v] ; i >= 1 ; -- i) { chk(D[i - 1], D[i]); } chk(ans[min(n >> 1, n - sz[v])], D[min(n >> 1, n - sz[v])] + 1 - d[v]); if (cl) { for (int i = 0 ; i <= pq[v] ; ++ i) { cur[i] = D[i] = D2[i] = -inf; } } } int H = 1; int t[N * 4]; void modify(int l, int r, int value) { for (l += H, r += H; l < r; l >>= 1, r >>= 1) { if (l&1) t[l] = max(t[l], value), l++; if (r&1) --r, t[r] = max(t[r], value); } } int query(int p) { int res = -inf; for (p += H; p > 0; p >>= 1) res = max(res, t[p]); return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n; while (H < n) H <<= 1; for (int i = 1 ; i < n ; ++ i) { int a, b; cin >> a >> b; g[a].emplace_back(b); g[b].emplace_back(a); } for (int i = 0 ; i < N ; ++ i) { D[i] = D2[i] = cur[i] = -inf; } precalc(1); const int HALF = n / 2; for (int i = 1 ; i <= n ; ++ i) { pq[i] = min(HALF, sz[i]); } dfs(1); { vector<pair<int,int>>vec; for (int i = 1 ; i <= n ; ++ i) { vec.emplace_back(n - sz[i], -i); vec.emplace_back(sz[i], i); } for (int i = 0 ; i < H * 2 ; ++ i) t[i] = -inf; sort(vec.rbegin(), vec.rend()); for (auto [wsz, i] : vec) { if (i < 0) { i = -i; modify(tin[i], tout[i], -d[i] + 1); } else { int mx = query(tin[i]); ans[sz[i]] = max(ans[sz[i]], mx + d[i]); } } } for (int i = n ; i >= 1 ; -- i) { ans[i - 1] = max(ans[i - 1], ans[i]); } for (int i = 1 ; i <= n ; ++ i) { if (i % 2 == 1) { cout << 1 << "\n"; continue; } cout << ans[i / 2] + 1 << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...