Submission #475708

#TimeUsernameProblemLanguageResultExecution timeMemory
475708blueMeetings 2 (JOI21_meetings2)C++17
100 / 100
673 ms53256 KiB
#include <iostream> #include <vector> #include <queue> #include <set> using namespace std; const int maxN = 200'000; const int logN = 19; int N; vector<int> edge[1+maxN]; int anc[1+maxN][1+logN]; vector<int> depth(1+maxN); void dfs(int u) { for(int v: edge[u]) { if(anc[u][0] == v) continue; anc[v][0] = u; depth[v] = depth[u] + 1; dfs(v); } } int lca(int u, int v) { if(depth[u] > depth[v]) swap(u, v); for(int e = logN; e >= 0; e--) { if(depth[ anc[v][e] ] >= depth[u]) v = anc[v][e]; } if(u == v) return u; for(int e = logN; e >= 0; e--) { if(anc[u][e] == anc[v][e]) continue; u = anc[u][e]; v = anc[v][e]; } u = anc[u][0]; return u; } int dist(int u, int v) { return depth[u] + depth[v] - 2*depth[lca(u, v)]; } int main() { cin >> N; for(int e = 1; e <= N-1; e++) { int A, B; cin >> A >> B; edge[A].push_back(B); edge[B].push_back(A); } anc[1][0] = anc[0][0] = 0; depth[1] = 1; dfs(1); for(int e = 1; e <= logN; e++) { for(int u = 0; u <= N; u++) { anc[u][e] = anc[ anc[u][e-1] ][e-1]; } } vector<int> added(N+1, 0); //add time int add_id = 0; vector<int> counter(N+1, 0); vector<int> leaf_size(1+N, 1); set<int> tbv[1+N]; int visit_count = 0; for(int u = 1; u <= N; u++) { if(edge[u].size() == 1) { tbv[1].insert(u); added[u] = 1; } } vector<int> suspicious; for(int s = 1; s <= N; s++) { for(int u: tbv[s]) { bool flag = 0; for(int v: edge[u]) { if(added[v]) continue; flag = 1; leaf_size[v] += leaf_size[u]; counter[v]++; if(counter[v] == edge[v].size() - 1) { // cerr << "adding " << v << " from " << u << '\n'; add_id++; added[v] = add_id; tbv[leaf_size[v]].insert(v); } } if(flag == 0) suspicious.push_back(u); } } // for(int s:suspicious) cerr << s << ' ' << leaf_size[s] << '\n'; // cerr << '\n'; // cerr << suspicious.size() << '\n'; // for(int s = 1; s <= N; s++) // { // cerr << "s = " << s << ": "; // for(int u: tbv[s]) cerr << u << ' '; // cerr << '\n'; // } vector<int> res(N+1, 1); int curr1 = -1, curr2 = -1; int J = N/2; for(int s = N; s >= 1; s--) { for(int u: tbv[s]) { // cerr << "adding " << u << '\n'; if(curr1 == -1) curr1 = u; else if(curr2 == -1) curr2 = u; else { // cerr << dist(u, curr1) << ' ' << dist(u, curr2) << ' ' << dist(curr1, curr2) << '\n'; if(dist(u, curr1) > dist(curr1, curr2)) { // cerr << "entered 1\n"; curr2 = u; } else if(dist(u, curr2) > dist(curr1, curr2)) { // cerr << "entered 2\n"; curr1 = u; } } if(curr1 == -1 || curr2 == -1) continue; // cerr << "diameter = " << curr1 << ' ' << curr2 << '\n'; // cerr << "min leaf size = " << min(leaf_size[curr1], leaf_size[curr2]) << ' ' << dist(curr1, curr2) + 1 << '\n'; // // cerr << "J = " << J << '\n'; while(J > min(leaf_size[curr1], leaf_size[curr2])) { J--; // cerr << "j--\n"; } if(J == min(leaf_size[curr1], leaf_size[curr2])) { res[2*J] = dist(curr1, curr2) + 1; } } } for(int q = 2*(N/2) - 2; q >= 2; q -= 2) res[q] = max(res[q], res[q+2]); for(int i = 1; i <= N; i++) cout << res[i] << ' '; cout << '\n'; }

Compilation message (stderr)

meetings2.cpp: In function 'int main()':
meetings2.cpp:116:31: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |                 if(counter[v] == edge[v].size() - 1)
meetings2.cpp:90:9: warning: unused variable 'visit_count' [-Wunused-variable]
   90 |     int visit_count = 0;
      |         ^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...