Submission #1010198

#TimeUsernameProblemLanguageResultExecution timeMemory
1010198PoPularPlusPlusMeetings 2 (JOI21_meetings2)C++17
0 / 100
2 ms7516 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb(x) push_back(x) #define mp(x,y) make_pair(x,y) #define all(x) x.begin(),x.end() #define vf first #define vs second const int mod = 1000000007; mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); const int N = 200004; vector<int> adj[N]; int siz[N]; bool vis[N]; int ans[N]; int mx[N]; void cal_siz(int node , int par){ siz[node] = 1; for(int i : adj[node]){ if(i!=par && !vis[i]){ cal_siz(i , node); siz[node] += siz[i]; } } } int centroid(int node , int par , int tot){ for(int i : adj[node]){ if(!vis[i] && i != par && siz[i] >= tot){ return centroid(i , node , tot); } } return node; } void dfs(int node , int par , int dis){ mx[siz[node]] = max(mx[siz[node]] , dis); for(int i : adj[node]){ if(i!=par && !vis[i])dfs(i , node , dis + 1); } } void centroid_decomposition(int node){ cal_siz(node , node); int tot = siz[node]; int root = centroid(node , node , (tot+1)/2); cal_siz(root,root); vector<pair<int,int>> v[tot + 2]; int mx_siz = 0; for(int i : adj[root]){ if(!vis[i]){ mx_siz = max(mx_siz , siz[i]); for(int j = 0; j <= siz[i]; j++){ mx[j] = -1; } dfs(i , root , 1); for(int j = 1; j <= siz[i]; j++){ //cout << mx[j] << ' '; v[j].pb(mp(mx[j],i)); sort(all(v[j]),greater<>()); while(v[j].size() > 2)v[j].pop_back(); } //cout << '\n'; } } v[tot-mx_siz].pb(mp(0,-1)); /*for(int i = tot; i >= 0; i--){ cout << i << '\n'; for(auto j : v[tot]){ cout << j.vf << ' ' << j.vs << '\n'; } }*/ for(int i = tot; i >= 0; i--){ for(auto j : v[i + 1]){ v[i].pb(j); } sort(all(v[i]),greater<>()); if(v[i].size() >= 2){ if(v[i][0].vs == v[i][1].vs){ v[i].erase(v[i].begin() + 1); } } if(v[i].size() >= 2){ if(v[i][0].vs == v[i][1].vs){ v[i].erase(v[i].begin()+1); } } if(v[i].size() >= 2 && v[i][0].vs != v[i][1].vs){ ans[2*i] = max(ans[2*i] , v[i][0].vf + v[i][1].vf + 1); } } vis[root] = 1; for(int i : adj[root]){ if(!vis[i]){ centroid_decomposition(i); } } } void solve(){ int n; cin >> n; for(int i = 0; i < n - 1; i++){ int a , b; cin >> a >> b; adj[a].pb(b); adj[b].pb(a); } memset(vis,0,sizeof vis); memset(ans,-1,sizeof ans); centroid_decomposition(1); for(int i = n; i > 0; i--){ if(i % 2 == 1){;} else { ans[i] = max(ans[i] , ans[i + 2]); } } for(int i = 1; i <= n; i++){ if(i % 2 == 1)cout << 1 << '\n'; else cout << ans[i] << '\n'; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); //int t; //cin >> t; //while(t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...