Submission #546427

#	Time	Username	Problem	Language	Result	Execution time	Memory
546427		cadmiumsky	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	3688 ms	48768 KiB

meetings2

#include <bits/stdc++.h>
#pragma GCC optimize("fast-math")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse3,sse4,avx,avx2")
#pragma GCC push_options
#pragma GCC pop_options
using namespace std;
const int nmax = 2e5 + 5;
vector<int> g[nmax]; 
int n;
int rez[nmax];
int supmem[nmax + 100], ptr;
 
namespace Centroid {
  int occ[nmax];
  int area[nmax];
  int nval[nmax];
  int depth[nmax];
  #define norm lasama
  map<pair<int, int> ,int> norm;
  map<int ,int> fpoz;
  namespace AINT {
    int aint[1048576];
    static int len;
    void clean(int node = 1, int cl = 1, int cr = len) {
      aint[node] = 0;
      if(cl == cr)
        return;
      int mid = cl + cr >> 1;
      clean(2 * node, cl, mid);
      clean(2 * node + 1, mid + 1, cr);
    }
    void init(int nlen) { 
      len = nlen; 
      clean();
    }
    void upd(int poz, int val, int node = 1, int cl = 1, int cr = len) {
      if(cl == cr)
        aint[node] = val;
      else {
        int mid = cl + cr >> 1;
        if(poz <= mid)
          upd(poz, val, 2 * node, cl, mid);
        else
          upd(poz, val, 2 * node + 1, mid + 1, cr);
        aint[node] = max(aint[2 * node], aint[2 * node + 1]);
      }
      return;
    } 
    int query(int poz, int node = 1, int cl = 1, int cr = len) {
      if(cr < poz)
        return 0;
      if(poz <= cl)
        return aint[node];
      int mid = cl + cr >> 1;
      return max(query(poz, 2 * node, cl, mid), query(poz, 2 * node + 1, mid + 1, cr));
    }
  };
  void initcentr(int node, int f) {
    area[node] = 1;
    for(auto x : g[node]) {
      if(occ[x] == 0 && x != f)
        initcentr(x, node), area[node] += area[x];
    }
    return;
  }
  int initdepth(int node, int f) {
    if(occ[node])
      return area[node];
    depth[node] = depth[f] + 1;
    area[node] = 1;
    for(auto x : g[node])
      if(x != f)
        area[node] += initdepth(x, node);
    return area[node];
  }
  int findcentr(int node, int f, int thresh) {
    for(auto x : g[node])  {
      if(occ[x] || x == f)
        continue;
      if(area[x] > thresh)
        return findcentr(x, node, thresh);
    }
    return node;
  }
  void aggr(int node, int f, int val) {
    if(val == -1)
      AINT::upd(nval[node], 0);
    else
      AINT::upd(nval[node], depth[node]);
    for(auto x : g[node])
      if(!occ[x] && x != f)
        aggr(x, node, val);
  }
  void bnorm(int node, int f) {
    norm[{area[node], node}];
    for(auto x : g[node]) if(!occ[x] && x != f) bnorm(x, node);
    return;
  }
  void query(int node, int f) {
    int x = AINT::query(fpoz[area[node]]);
    if(x > 0)
      rez[(area[node]) * 2] = max(rez[(area[node]) * 2], x + depth[node] - 1);
    for(auto x : g[node]) if(!occ[x] && x != f) query(x, node);
    return;
  }
  void mkcentr(int node) {
    //cerr << "++++++\n" << node << "\n=====\n";
    int temp;
    initcentr(node, node);
    node = findcentr(node, node, area[node] / 2);
    //cerr << "Centroid is: " << node << '\n';
    depth[node] = 0;
    initdepth(node, node);
    for(int x, i = 0; i < g[node].size(); i++) {
      if(occ[g[node][i]]) {
        swap(g[node][i], g[node].back());
        g[node].pop_back();
        i--;
        continue;
      }
      x = g[node][i];
      norm[{n - area[x], node}];
      bnorm(x, node);
    }
    temp = 0;
    for(auto &[a, b] : norm) {
      b = ++temp;
      if(fpoz.find(a.first) == fpoz.end())
        fpoz[a.first] = b;
      nval[a.second] = b;
    }
    if(temp != 0) {
      AINT::init(temp);
      for(int i = 0; i < g[node].size(); i++)
        aggr(g[node][i], node, 1);
      for(int i = 0, x; i < g[node].size(); i++) {
        x = g[node][i];
        aggr(x, node, -1);
        AINT::upd(temp = norm[{n - area[x], node}], depth[node]);
        query(x, node);
        AINT::upd(temp, 0);
        aggr(x, node, 1);
      }
    }
    fpoz.clear();
    norm.clear();
    occ[node] = 1;
    int L = ptr, R;
    for(auto x : g[node])
      supmem[ptr++] = area[x];
    R = ptr;
    for(auto x : g[node]) {
      area[node] = n - supmem[L++];
      mkcentr(x);
    }
  }
}

int what[nmax];

mt19937 rng(time(0));
int rnd(int x) {
  return rng() % x;
}

int main() {
  srand(time(0));
  cin >> n;
  for(int i = 1; i <= n; i++)
    what[i] = i;
  random_shuffle(what + 1, what + n + 1, rnd);
  for(int x, y, i = 1; i < n; i++) {
    cin >> x >> y;
    x = what[x];
    y = what[y];
    g[x].push_back(y);
    g[y].push_back(x);
  }
  Centroid::mkcentr(1);
  for(int i = n; i > 0; i--) {
    if(i % 2 == 0)
      rez[i] = max({1, rez[i + 2], rez[i]});
    else
      rez[i] = 1;
  }
  //cout << "1\n" << 2 + rez[2] << '\n';
  for(int i = 1; i <= n; i++)
    cout << rez[i] << '\n';
}

Compilation message (stderr)

meetings2.cpp: In function 'void Centroid::AINT::clean(int, int, int)':
meetings2.cpp:29:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |       int mid = cl + cr >> 1;
      |                 ~~~^~~~
meetings2.cpp: In function 'void Centroid::AINT::upd(int, int, int, int, int)':
meetings2.cpp:41:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         int mid = cl + cr >> 1;
      |                   ~~~^~~~
meetings2.cpp: In function 'int Centroid::AINT::query(int, int, int, int)':
meetings2.cpp:55:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |       int mid = cl + cr >> 1;
      |                 ~~~^~~~
meetings2.cpp: In function 'void Centroid::mkcentr(int)':
meetings2.cpp:115:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for(int x, i = 0; i < g[node].size(); i++) {
      |                       ~~^~~~~~~~~~~~~~~~
meetings2.cpp:127:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  127 |     for(auto &[a, b] : norm) {
      |               ^
meetings2.cpp:135:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |       for(int i = 0; i < g[node].size(); i++)
      |                      ~~^~~~~~~~~~~~~~~~
meetings2.cpp:137:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |       for(int i = 0, x; i < g[node].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~
meetings2.cpp:149:18: warning: variable 'R' set but not used [-Wunused-but-set-variable]
  149 |     int L = ptr, R;
      |                  ^

• Subtask 1: 4 / 4
• Subtask 2: 16 / 16
• Subtask 3: 80 / 80