제출 #952241

#제출 시각아이디문제언어결과실행 시간메모리
952241GrindMachineMeetings 2 (JOI21_meetings2)C++17
0 / 100
7 ms19260 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) (int)a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x,y) ((x+y-1)/(y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) #define rev(i,s,e) for(int i = s; i >= e; --i) #define trav(i,a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a,b); } template<typename T> void amax(T &a, T b) { a = max(a,b); } #ifdef LOCAL #include "debug.h" #else #define debug(x) 42 #endif /* */ const int MOD = 1e9 + 7; const int N = 2e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; vector<ll> adj[N]; vector<ll> subsiz(N), depth(N); void dfs1(ll u, ll p){ subsiz[u] = 1; trav(v,adj[u]){ if(v == p) conts; depth[v] = depth[u]+1; dfs1(v,u); subsiz[u] += subsiz[v]; } } map<ll,ll> mp[N]; vector<ll> ans(N); void dfs2(ll u, ll p){ pll best = {-1,-1}; trav(v,adj[u]){ if(v == p) conts; pll px = {subsiz[v],v}; amax(best,px); } ll heavy = best.ss; if(heavy == -1){ mp[u][subsiz[u]] = depth[u]; return; } dfs2(heavy,u); swap(mp[u],mp[heavy]); trav(v,adj[u]){ if(v == p or v == heavy) conts; dfs2(v,u); for(auto [x,d1] : mp[v]){ // x <= y auto it = mp[u].lower_bound(x); if(it != mp[u].end()){ auto [y,d2] = *it; amax(ans[x],d1+d2-2*depth[u]); } // x > y if(it != mp[u].begin()){ it--; auto [y,d2] = *it; amax(ans[y],d1+d2-2*depth[u]); } } for(auto [x,d] : mp[v]){ auto it = mp[u].lower_bound(x); if(it != mp[u].end() and it->second >= d) conts; mp[u][x] = d; it = mp[u].find(x); vector<ll> torem; while(it != mp[u].begin()){ it--; if(it->second > d) break; torem.pb(it->first); } trav(y,torem){ mp[u].erase(y); } } } { ll x = subsiz[u], d = depth[u]; auto it = mp[u].lower_bound(x); if(!(it != mp[u].end() and it->second >= d)){ mp[u][x] = d; it = mp[u].find(x); vector<ll> torem; while(it != mp[u].begin()){ it--; if(it->second > d) break; torem.pb(it->first); } trav(y,torem){ mp[u].erase(y); } } } { ll mx = subsiz[1]-subsiz[u]; auto it = mp[u].lower_bound(mx); if(it != mp[u].end()){ auto [x,d] = *it; amax(ans[mx],d-depth[u]+1); } } } vector<pll> ances; void dfs3(ll u, ll p){ ances.pb({subsiz[1]-subsiz[u],u}); auto it = upper_bound(all(ances),make_pair(subsiz[u],-1ll)); if(it != ances.end()){ ll v = it->second; amax(ans[subsiz[u]],depth[u]-depth[v]+1); } trav(v,adj[u]){ if(v == p) conts; dfs3(v,u); } ances.pop_back(); } void solve(int test_case) { ll n; cin >> n; rep1(i,n-1){ ll u,v; cin >> u >> v; adj[u].pb(v), adj[v].pb(u); } dfs1(1,-1); dfs2(1,-1); dfs3(1,-1); rev(i,n,1) amax(ans[i],ans[i+1]); rep1(i,n){ if(i&1) cout << 1 << endl; else cout << ans[i/2]+1 << endl; } } int main() { fastio; int t = 1; // cin >> t; rep1(i, t) { solve(i); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...