Submission #550089

#	Time	Username	Problem	Language	Result	Execution time	Memory
550089		cig32	Meetings 2 (JOI21_meetings2)	C++17	20 / 100	4048 ms	178824 KiB

meetings2

#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 2e5 + 10;
const int MOD = 998244353;
#define ll __int128
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
ll read() { int x; cin >> x; return (ll)x; }
long long bm(long long b, long long p) {
  if(p==0) return 1 % MOD;
  long long r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
long long inv(long long b) { 
  return bm(b, MOD-2);
}
long long f[MAXN];
long long nCr(int n, int r) { 
  long long ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}
void precomp() { for(int i=0; i<MAXN; i++) f[i] = (i == 0 ? 1 % MOD : (f[i-1] * i) % MOD); }
int fastlog(int x) {
  return (x == 0 ? -1 : 32 - __builtin_clz(x) - 1);
}
void gay(int i) { cout << "Case #" << i << ": "; }
vector<int> adj[MAXN];
int n;
vector<int> e;
unordered_map<int, int> sz[MAXN]; // (node, par)
int dep[MAXN];
int dfs(int node, int prv) {
  int r = 1;
  dep[node] = (prv == -1 ? 0 : dep[prv] + 1);
  e.push_back(node);
  for(int x: adj[node]) {
    if(x != prv) {
      int d = dfs(x, node);
      sz[x][node] = d;
      sz[node][x] = n - d;
      r += d;
      e.push_back(node);
    }
  }
  return r;
}
int l[MAXN], r[MAXN];
pair<int, int> st[19][2*MAXN];
int dist(int x, int y) {
  int m1 = min(l[x], l[y]);
  int m2 = max(r[x], r[y]);
  int k = 32 - __builtin_clz(m2 - m1 + 1) - 1;
  int lca = min(st[k][m1], st[k][m2 - (1<<k) + 1]).second;
  return dep[x] + dep[y] - 2 * dep[lca];
}
void solve(int tc) {
  cin >> n;
  for(int i=1; i<n; i++) {
    int a, b;
    cin >> a >> b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  dfs(1, -1);              
  for(int i=0; i<e.size(); i++) r[e[i]] = i;
  for(int i=e.size()-1; i>=0; i--) l[e[i]] = i;
  for(int i=0; i<e.size(); i++) st[0][i] = {dep[e[i]], e[i]};
  for(int i=1; i<19; i++) {
    for(int j=0; j<e.size(); j++) {
      if(j+(1<<i)-1 < e.size()) st[i][j] = min(st[i-1][j], st[i-1][j+(1<<(i-1))]);
    }
  }
  int ans[n + 1];
  for(int i=1; i<=n; i++) ans[i] = 1;
  for(int i=1; i<=n; i++) {
    for(int j=i+1; j<=n; j++) {
      for(int x: adj[i]) {
        if(dist(i, x) + dist(x, j) == dist(i, j)) {
          for(int y: adj[j]) {
            if(dist(i, y) + dist(y, j) == dist(i, j)) {
              int uwu = dist(i, j) + 1;
              int mi = min(sz[i][x], sz[j][y]) * 2;
              ans[mi] = max(ans[mi], uwu);
            }
          }
        }
      }
    }
  }
  for(int i=n; i>=4; i--) {
    if(!(i&1)) {
      ans[i - 2] = max(ans[i - 2], ans[i]);
    }
  }
  for(int i=1; i<=n; i++) cout << ans[i] << "\n";
}
int32_t main() {
  precomp();
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
} 
// I don't know geometry.

Compilation message (stderr)

meetings2.cpp: In function 'void solve(long long int)':
meetings2.cpp:69:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   for(int i=0; i<e.size(); i++) r[e[i]] = i;
      |                ~^~~~~~~~~
meetings2.cpp:71:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |   for(int i=0; i<e.size(); i++) st[0][i] = {dep[e[i]], e[i]};
      |                ~^~~~~~~~~
meetings2.cpp:73:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int j=0; j<e.size(); j++) {
      |                  ~^~~~~~~~~
meetings2.cpp:74:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |       if(j+(1<<i)-1 < e.size()) st[i][j] = min(st[i-1][j], st[i-1][j+(1<<(i-1))]);
      |          ~~~~~~~~~~~^~~~~~~~~~

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