Submission #752149

#TimeUsernameProblemLanguageResultExecution timeMemory
752149Sam_a17Meetings 2 (JOI21_meetings2)C++17
100 / 100
2578 ms41404 KiB
#define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> //#include "temp.cpp" #include <cstdio> using namespace std; #ifndef ONLINE_JUDGE #define dbg(x) cerr << #x <<" "; print(x); cerr << endl; #else #define dbg(x) #endif #define sz(x) (int((x).size())) #define len(x) (int)x.length() #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define clr(x) (x).clear() #define blt(x) __builtin_popcount(x) #define uniq(x) x.resize(unique(all(x)) - x.begin()); #define pb push_back #define popf pop_front #define popb pop_back #define ld long double #define ll long long void print(long long t) {cerr << t;} void print(int t) {cerr << t;} void print(string t) {cerr << t;} void print(char t) {cerr << t;} void print(double t) {cerr << t;} void print(unsigned long long t) {cerr << t;} void print(long double t) {cerr << t;} template <class T, class V> void print(pair <T, V> p); template <class T> void print(vector <T> v); template <class T> void print(set <T> v); template <class T, class V> void print(map <T, V> v); template <class T> void print(multiset <T> v); template <class T> void print(T v[],T n) {cerr << "["; for(int i = 0; i < n; i++) {cerr << v[i] << " ";} cerr << "]";} template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";} template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";} template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";} #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #define nl '\n' // for random generations mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count()); // mt19937 myrand(131); // for grid problems int dx[8] = {-1,0,1,0,1,-1,1,-1}; int dy[8] = {0,1,0,-1,1,1,-1,-1}; // lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6 void fastIO() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); } // file in/out void setIO(string str = "") { fastIO(); if (str != "") { freopen((str + ".in").c_str(), "r", stdin); freopen((str + ".out").c_str(), "w", stdout); } else { // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); } } // Indexed Set template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const int N = 2e5 + 10, LOG = 21; vector<int> adj[N]; bool used[N]; int n, sz[N], most; int compSize; struct segTreeMax { vector<long long> mTree; int size; void init(long long n) { size = 1; while(size < n) { size *= 2; } mTree.assign(2 * size - 1, -1); } void upd(int u, long long v, int x, int lx, int rx) { // set value at pos u if(rx - lx == 1) { if(v == -1) { mTree[x] = -1; } else { mTree[x] = max(mTree[x], v); } return; } int m = (lx + rx) / 2; if(u < m) { upd(u, v, 2 * x + 1, lx, m); }else { upd(u, v, 2 * x + 2, m, rx); } mTree[x] = max(mTree[2 * x + 1], mTree[2 * x + 2]); } void upd(int u, long long v) { upd(u, v, 0, 0, size); } long long qry (int l, int r, int x, int lx, int rx) { // range queries if(l >= rx || lx >= r) { return -1; } if(lx >= l && r >= rx) { return mTree[x]; } int m = (rx + lx) / 2; long long s1 = qry(l, r, 2 * x + 1, lx, m); long long s2 = qry(l, r, 2 * x + 2, m, rx); return max(s1, s2); } long long qry(int l, int r) { return qry(l, r, 0, 0, size); } }; segTreeMax seg_max; void dfs_sz(int node, int parent) { sz[node] = 1, compSize++; for(auto i: adj[node]) { if(i == parent || used[i]) continue; dfs_sz(i, node); sz[node] += sz[i]; } } int get_centroid(int node, int parent) { for(auto i: adj[node]) { if(i == parent || used[i]) continue; if(2 * sz[i] > compSize) { return get_centroid(i, node); } } return node; } int centroid(int u) { compSize = 0; dfs_sz(u, 0); int p = get_centroid(u, 0); if(!most) most = p; dfs_sz(p, 0); return p; } bool use[N]; vector<pair<int, int>> curr; vector<int> full; int ans[N], bb; void solve(int node, int parent, int depth, int lim) { if(depth) { if(!use[sz[node]]) { full.push_back(sz[node]); use[sz[node]] = true; } curr.push_back({sz[node], depth}); ans[2 * min(sz[node], lim)] = max(ans[2 * min(sz[node], lim)], depth); } for(auto i: adj[node]) { if(i == parent || used[i]) continue; if(!depth) { solve(i, node, depth + 1, n - sz[i]); } else { solve(i, node, depth + 1, lim); } if(parent) continue; for(auto j: curr) { int max_dep = seg_max.qry(j.first, n + 1); if(max_dep != -1) { ans[j.first * 2] = max(ans[j.first * 2], max_dep + j.second); } } for(auto j: curr) { seg_max.upd(j.first, j.second); } curr.clear(); } } void centroid_decomposition() { queue<int> q; q.push(1); while(!q.empty()) { auto u = q.front(); q.pop(); int get = centroid(u); solve(get, 0, 0, 0); for(auto i: full) { use[i] = false; seg_max.upd(i, -1); } full.clear(); reverse(all(adj[get])); solve(get, 0, 0, 0); for(auto i: full) { use[i] = false; seg_max.upd(i, -1); } full.clear(); used[get] = true; for(auto i: adj[get]) { if(used[i] || sz[i] == 1) continue; q.push(i); } } } void solve_() { cin >> n; seg_max.init(n + 5); for(int i = 1; i <= n - 1; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } centroid_decomposition(); for(int i = n; i >= 1; i--) { ans[i] = max(ans[i], ans[i + 1]); } for(int i = 1; i <= n; i++) { if(i & 1) { cout << 1 << '\n'; } else { cout << ans[i] + 1 << '\n'; } } } int main() { setIO(); auto solve = [&](int test_case)-> void { while(test_case--) { solve_(); } }; int test_cases = 1; // cin >> test_cases; solve(test_cases); return 0; }

Compilation message (stderr)

meetings2.cpp: In function 'void setIO(std::string)':
meetings2.cpp:70:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
meetings2.cpp:71:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...