oj.uz

Submission #550089

# Submission time Handle Problem Language Result Execution time Memory
550089 2022-04-17T08:33:35 Z cig32 Meetings 2 (JOI21_meetings2) C++17
20 / 100
 4000 ms 178824 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 17536 KB Output is correct
2 Correct 12 ms 17492 KB Output is correct
3 Correct 16 ms 17496 KB Output is correct
4 Correct 11 ms 17620 KB Output is correct
5 Correct 12 ms 17560 KB Output is correct
6 Correct 12 ms 17524 KB Output is correct
7 Correct 12 ms 17620 KB Output is correct
8 Correct 11 ms 17620 KB Output is correct
9 Correct 13 ms 17608 KB Output is correct
10 Correct 13 ms 17492 KB Output is correct
11 Correct 13 ms 17620 KB Output is correct
12 Correct 14 ms 17556 KB Output is correct
13 Correct 13 ms 17536 KB Output is correct
14 Correct 15 ms 17620 KB Output is correct
15 Correct 12 ms 17556 KB Output is correct
16 Correct 12 ms 17544 KB Output is correct
17 Correct 11 ms 17620 KB Output is correct
18 Correct 11 ms 17548 KB Output is correct
19 Correct 11 ms 17620 KB Output is correct
20 Correct 12 ms 17548 KB Output is correct
21 Correct 12 ms 17620 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 17536 KB Output is correct
2 Correct 12 ms 17492 KB Output is correct
3 Correct 16 ms 17496 KB Output is correct
4 Correct 11 ms 17620 KB Output is correct
5 Correct 12 ms 17560 KB Output is correct
6 Correct 12 ms 17524 KB Output is correct
7 Correct 12 ms 17620 KB Output is correct
8 Correct 11 ms 17620 KB Output is correct
9 Correct 13 ms 17608 KB Output is correct
10 Correct 13 ms 17492 KB Output is correct
11 Correct 13 ms 17620 KB Output is correct
12 Correct 14 ms 17556 KB Output is correct
13 Correct 13 ms 17536 KB Output is correct
14 Correct 15 ms 17620 KB Output is correct
15 Correct 12 ms 17556 KB Output is correct
16 Correct 12 ms 17544 KB Output is correct
17 Correct 11 ms 17620 KB Output is correct
18 Correct 11 ms 17548 KB Output is correct
19 Correct 11 ms 17620 KB Output is correct
20 Correct 12 ms 17548 KB Output is correct
21 Correct 12 ms 17620 KB Output is correct
22 Correct 1344 ms 20212 KB Output is correct
23 Correct 1406 ms 20216 KB Output is correct
24 Correct 1268 ms 20192 KB Output is correct
25 Correct 1320 ms 20192 KB Output is correct
26 Correct 1255 ms 20180 KB Output is correct
27 Correct 1317 ms 20220 KB Output is correct
28 Correct 1356 ms 20224 KB Output is correct
29 Correct 1397 ms 20220 KB Output is correct
30 Correct 1374 ms 20220 KB Output is correct
31 Correct 1264 ms 20216 KB Output is correct
32 Correct 1274 ms 20300 KB Output is correct
33 Correct 1198 ms 20448 KB Output is correct
34 Correct 1178 ms 20236 KB Output is correct
35 Correct 1059 ms 20272 KB Output is correct
36 Correct 1173 ms 20252 KB Output is correct
37 Correct 1103 ms 20276 KB Output is correct
38 Correct 1227 ms 20436 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 17536 KB Output is correct
2 Correct 12 ms 17492 KB Output is correct
3 Correct 16 ms 17496 KB Output is correct
4 Correct 11 ms 17620 KB Output is correct
5 Correct 12 ms 17560 KB Output is correct
6 Correct 12 ms 17524 KB Output is correct
7 Correct 12 ms 17620 KB Output is correct
8 Correct 11 ms 17620 KB Output is correct
9 Correct 13 ms 17608 KB Output is correct
10 Correct 13 ms 17492 KB Output is correct
11 Correct 13 ms 17620 KB Output is correct
12 Correct 14 ms 17556 KB Output is correct
13 Correct 13 ms 17536 KB Output is correct
14 Correct 15 ms 17620 KB Output is correct
15 Correct 12 ms 17556 KB Output is correct
16 Correct 12 ms 17544 KB Output is correct
17 Correct 11 ms 17620 KB Output is correct
18 Correct 11 ms 17548 KB Output is correct
19 Correct 11 ms 17620 KB Output is correct
20 Correct 12 ms 17548 KB Output is correct
21 Correct 12 ms 17620 KB Output is correct
22 Correct 1344 ms 20212 KB Output is correct
23 Correct 1406 ms 20216 KB Output is correct
24 Correct 1268 ms 20192 KB Output is correct
25 Correct 1320 ms 20192 KB Output is correct
26 Correct 1255 ms 20180 KB Output is correct
27 Correct 1317 ms 20220 KB Output is correct
28 Correct 1356 ms 20224 KB Output is correct
29 Correct 1397 ms 20220 KB Output is correct
30 Correct 1374 ms 20220 KB Output is correct
31 Correct 1264 ms 20216 KB Output is correct
32 Correct 1274 ms 20300 KB Output is correct
33 Correct 1198 ms 20448 KB Output is correct
34 Correct 1178 ms 20236 KB Output is correct
35 Correct 1059 ms 20272 KB Output is correct
36 Correct 1173 ms 20252 KB Output is correct
37 Correct 1103 ms 20276 KB Output is correct
38 Correct 1227 ms 20436 KB Output is correct
39 Execution timed out 4048 ms 178824 KB Time limit exceeded
40 Halted 0 ms 0 KB -