oj.uz

Submission #593152

# Submission time Handle Problem Language Result Execution time Memory
593152 2022-07-10T13:18:13 Z SuffixAutomata Meetings 2 (JOI21_meetings2) C++17
0 / 100
 7 ms 10068 KB 
#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using ll = long long;
using pii = pair<int, int>;
//#define int ll
const int MOD = 1000000007;

vector<int> elist[200005];

int fa[200005], sz[200005], dep[200005];
pii mxs[200005];

int dfss(int u, int f) {
  fa[u] = f, sz[u] = 1;
  for (int v : elist[u])
    if (v != f)
      sz[u] += dfss(v, u), mxs[u] = max(mxs[u], {sz[v], v});
  return sz[u];
}

int ans[100005];

int sub[200005];

void dfs2(int u, int f, int x) {
  dep[u] = dep[f] + 1;
  sub[u] = x;
  for (int v : elist[u])
    if (v != f)
      dfs2(v, u, x);
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 1; i <= n - 1; i++) {
    int a, b;
    cin >> a >> b;
    elist[a].pb(b);
    elist[b].pb(a);
  }
  if (n == 1) {
    cout << 1 << endl;
    return 0;
  }
  dfss(1, 0);
  int rt = 1;
  while (mxs[rt].fi >= n / 2)
    rt = mxs[rt].se;
  dfss(rt, 0);
  for (int i : elist[rt])
    dfs2(i, rt, i);
  vector<pii> ps;
  for (int i = 1; i <= n; i++)
    if (i != rt) {
      ps.pb({sz[i], i});
      assert(sz[i] < n / 2);
    }
  sort(all(ps));
  vector<int> active(n + 1), mdp(n + 1);
  multiset<int> mdp2;
  mdp2.insert(0);
  for (int i : elist[rt])
    mdp2.insert(mdp[i]);
  for (int i = n; i >= 1; i--) {
    while (ps.size() && ps.back().fi >= i) {
      int u = sub[ps.back().se];
      mdp2.erase(mdp2.find(mdp[u]));
      mdp[u] = max(mdp[u], dep[ps.back().se]);
      mdp2.insert(mdp[u]);
      ps.pop_back();
    }
    if (i <= n / 2)
      ans[i] = *mdp2.rbegin() + *next(mdp2.rbegin()) + 1;
  }
  for (int i = n / 2; i >= 1; i--)
    ans[i] = max(ans[i], ans[i + 1]);
  for (int i = 1; i <= n; i++) {
    if (i % 2)
      cout << "1\n";
    else
      cout << ans[i / 2] << "\n";
  }
  return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Runtime error 7 ms 10068 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Runtime error 7 ms 10068 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Runtime error 7 ms 10068 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -