oj.uz

Submission #593144

# Submission time Handle Problem Language Result Execution time Memory
593144 2022-07-10T12:46:38 Z SuffixAutomata Meetings 2 (JOI21_meetings2) C++17
0 / 100
 2 ms 4948 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];

pii dfs1(int u, int f) {
  pii ans = {-1, u};
  for (int v : elist[u])
    if (v != f)
      ans = max(ans, dfs1(v, u));
  ans.fi++;
  return ans;
}

int fa[200005], sz[200005], dep[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);
  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);
  }
  int L = dfs1(1, 0).se;
  int R = dfs1(L, 0).se;
  dfss(L, 0);
  vector<int> lrp = {R};
  int R2 = R;
  while (R2 != L)
    lrp.pb(R2 = fa[R2]);
  int rt = lrp[lrp.size() / 2];
  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});
  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 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Incorrect 2 ms 4948 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Incorrect 2 ms 4948 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Incorrect 2 ms 4948 KB Output isn't correct
6 Halted 0 ms 0 KB -