Submission #386379

#TimeUsernameProblemLanguageResultExecution timeMemory
386379Mamnoon_SiamMeetings 2 (JOI21_meetings2)C++17
100 / 100
2366 ms86664 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ii = pair<int, int>; using vi = vector<int>; #define all(v) begin(v), end(v) #define sz(v) (int)(v).size() #define fi first #define se second /** * Author: Lucian Bicsi * Date: 2017-10-31 * License: CC0 * Source: folklore * Description: Zero-indexed max-tree. Bounds are inclusive to the left and exclusive to the right. Can be changed by modifying T, f and unit. * Time: O(\log N) * Status: stress-tested */ struct Tree { typedef int T; static constexpr T unit = INT_MIN; T f(T a, T b) { return max(a, b); } // (any associative fn) vector<T> s; int n; Tree(int _n = 0, T def = unit) : s(2*_n, def), n(_n) {} void update(int pos, T val) { pos--; pos += n; s[pos] = f(s[pos], val); for (; pos >>= 1;) // do u mean += val??? s[pos] = f(s[pos << 1], s[pos << 1 | 1]); } T query(int b, int e) { // query [b, e) b--; T ra = unit, rb = unit; for (b += n, e += n; b < e; b >>= 1, e >>= 1) { if (b & 1) ra = f(ra, s[b++]); if (e & 1) rb = f(s[--e], rb); } return f(ra, rb); } void reset(int pos) { pos--; pos += n; s[pos] = unit; for (; pos >>= 1;) // do u mean += val??? s[pos] = f(s[pos << 1], s[pos << 1 | 1]); } } tr; const int N = 2e5 + 5; const int lg = 18; using tri = array<int, 3>; // index, length, size vector<ii> upds; int n; int sub[N], in[N], tym = 0, lvl[N], dp[lg][N]; vi g[N]; int sub0[N]; int vis[N]; // already centroid bool isanc(int u, int v) { // is u v's anc? return in[u] <= in[v] and in[v] < in[u]+sub[u]; } int __lca(int u, int v) { if(lvl[u] > lvl[v]) swap(u, v); int d = lvl[v] - lvl[u]; for(int i = 0; i < lg; ++i) if(d >> i & 1) v = dp[i][v]; if(u == v) return u; for(int i = lg-1; i >= 0; --i) if(dp[i][u] != dp[i][v]) u = dp[i][u], v = dp[i][v]; return dp[0][u]; } int kth_anc(int u, int k) { for(int i = 0; i < lg; ++i) if(k >> i & 1) u = dp[i][u]; return u; } int dis(int u, int v) { return lvl[u] + lvl[v] - 2*lvl[__lca(u,v)]; } int directed_size(int u, int v) { // it MUST be and EDGE return in[u] < in[v] ? sub0[v] : n - sub0[u]; } void dfs_sizes(int u, int dad) { sub[u] = 1; for(int v : g[u]) if(!vis[v] and v != dad) { dfs_sizes(v, u); sub[u] += sub[v]; } } int centroid(int u, int dad, int thr) { for(int v : g[u]) if(!vis[v] and v != dad and sub[v] > thr) { return centroid(v, u, thr); } return u; } void dfs_calc(int u, int dad, int level, vector<ii>& bag) { bag.emplace_back(level, directed_size(dad, u)); for(int v : g[u]) if(!vis[v] and v != dad) { dfs_calc(v, u, level+1, bag); } } int decompose(int u) { dfs_sizes(u, -1); int cen = centroid(u, -1, sub[u]/2); vi back; vector<vector<ii>> bags; for(int v : g[cen]) if(!vis[v]) { back.emplace_back(directed_size(v, cen)); bags.push_back({}); dfs_calc(v, cen, 1, bags.back()); } for(int i = 0; i < sz(back); ++i) { for(auto& [len, size] : bags[i]) { int mx = tr.query(size, n); if(mx != INT_MIN) { upds.emplace_back(mx + len + 1, size); } } for(auto& [len, size] : bags[i]) { tr.update(size, len); } } for(int i = 0; i < sz(back); ++i) { for(auto& [len, size] : bags[i]) { tr.reset(size); } } for(int i = sz(back)-1; i >= 0; --i) { for(auto& [len, size] : bags[i]) { int mx = tr.query(size, n); if(mx != INT_MIN) { upds.emplace_back(mx + len + 1, size); } } for(auto& [len, size] : bags[i]) { tr.update(size, len); } } for(int i = 0; i < sz(back); ++i) { for(auto& [len, size] : bags[i]) { tr.reset(size); } } for(int i = 0; i < sz(back); ++i) { for(auto& [len, size] : bags[i]) { upds.emplace_back(len+1, min(size, back[i])); } } vis[cen] = 1; for(int v : g[cen]) if(!vis[v]) { decompose(v); } return cen; } void dfs_initial(int u, int dad) { in[u] = ++tym; sub0[u] = 1; lvl[u] = dad ? lvl[dad] + 1 : 0; dp[0][u] = dad; for(int i = 1; i < lg; ++i) dp[i][u] = dp[i-1][dp[i-1][u]]; for(int v : g[u]) if(v != dad) { dfs_initial(v, u); sub0[u] += sub0[v]; } } int main(int argc, char const *argv[]) { #ifdef LOCAL freopen("in", "r", stdin); #endif upds.reserve(3*lg*N); scanf("%d", &n); tr = Tree(n); // assert(n <= 4000); for(int i = 1; i < n; ++i) { int u, v; scanf("%d %d", &u, &v); g[u].emplace_back(v); g[v].emplace_back(u); } dfs_initial(1, 0); decompose(1); vi ans(n+1, 1); sort(all(upds)); reverse(all(upds)); int ptr = 0; for(auto [d, mn] : upds) { while(ptr < mn) { ans[2*(++ptr)] = d; } } for(int i = 1; i <= n; ++i) printf("%d\n", ans[i]); return 0; }

Compilation message (stderr)

meetings2.cpp: In function 'int main(int, const char**)':
meetings2.cpp:185:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  185 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
meetings2.cpp:189:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  189 |     int u, v; scanf("%d %d", &u, &v);
      |               ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...