Submission #1243300

#TimeUsernameProblemLanguageResultExecution timeMemory
1243300Sam_arvandiMeetings 2 (JOI21_meetings2)C++20
0 / 100
3 ms4936 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define FOR(i, j, n) for (int i = j; i<= n; i++) #define ROF(i, n, j) for (int i = n; i>= j; i--) #define pb push_back #define mp make_pair #define S second #define F first #define IOS ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0) /* #pragma GCC optimization("Ofast, unroll-loops") #pragma GCC target("avx2") #pragma GCC target("bmi") #pragma GCC target("bmi2") #pragma GCC target("lzcnt") */ const int mn = 2e5 + 5; pii max1[mn], max2[mn]; int k[mn]; bool mark[mn]; int siz[mn], h[mn], out[mn]; vector<int> a[mn]; void dfs(int u, int par = 0) { siz[u] = 1; if (par != 0) h[u] = h[par]+1; for(auto v: a[u]) { if (mark[v] or v == par) continue; dfs(v, u); siz[u] += siz[v]; } return; } int dfs2(int u, int n , int par = 0) { bool flag = 1; for(auto v: a[u]) { if (mark[v] or v == par) continue; int tmp = dfs2(v, n, u); if (tmp > 0) return tmp; if (siz[v] > n/2) flag = 0; } if (flag and siz[u] >= (n+1)/2) return u; return 0; } vector<int> melat; void dfs3(int u, int par, int x) { k[u] = x; melat.pb(u); if (max1[siz[u]].F <= h[u]) { if (max1[siz[u]].S != x) max2[siz[u]] = max1[siz[u]]; max1[siz[u]] = mp(h[u], x); } else if (h[u] > max2[siz[u]].F and x != max2[siz[u]].S) { max2[siz[u]] = mp(h[u], x); } for(auto v: a[u]) { if (mark[v] or v == par) continue; dfs3(v, u, x); } return; } void solve(int u) { h[u] = 0; dfs(u); int n = siz[u]; int cen = dfs2(u, n); //cout << cen << ' ' << n << endl; h[cen] = 0; dfs(cen); for(auto v: a[cen]) { if (mark[v]) continue; dfs3(v, cen, v); } ROF(i, n-1, 1) { vector<pii> tmp; tmp.pb(max1[i]); tmp.pb(max2[i]); tmp.pb(max1[i+1]); tmp.pb(max2[i+1]); sort(tmp.begin(), tmp.end()); max1[i] = tmp[3]; if (tmp[2].S != max1[i].S) { max2[i] = tmp[2]; } else if (tmp[1].S != max1[i].S) max2[i] = tmp[1]; else max2[i] = tmp[0]; } for(auto v: melat) { if (max1[siz[v]].S != k[v]) out[siz[v]] = max(out[siz[v]], h[v]+max1[siz[v]].F); else out[siz[v]] = max(out[siz[v]], h[v]+max2[siz[v]].F); if (n-siz[k[v]] >= siz[v]) out[siz[v]] = max(out[siz[v]], h[v]); } mark[cen] = 1; melat.clear(); FOR(i, 1, n) { max1[i] = max2[i] = mp(0, 0); } return; for(auto v: a[cen]) { if (!mark[v]) { solve(v); } } return; } signed main() { IOS; int n, u, v; cin >> n; FOR(i, 1, n-1) { cin>> u >> v; a[u].pb(v); a[v].pb(u); } solve(1); ROF(i, n, 1) { out[i] = max(out[i], out[i+1]); } FOR(i, 1, n) { if (i%2) cout << 1 << ' '; else cout << out[i/2]+1 << ' '; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...