Submission #873066

#	Time	Username	Problem	Language	Result	Execution time	Memory
873066		sleepntsheep	Meetings 2 (JOI21_meetings2)	C++17	0 / 100	1 ms	6492 KiB

meetings2

#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using i64 = long long;
using f80 = long double;
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false)

#define N 200000
#define ALL(x) x.begin(), x.end()

int n, ne, h[N], a[N], b[N], c[N], sz[N], sts[N], alloc, ans[N+1], dd[N];
struct { int v, l; } g[2*N-1];

inline __attribute__((always_inline)) void add_edge(int u, int v)
{
    g[++ne] = {v, h[u]}; h[u] = ne;
}

void dfsd(int u, int p)
{
    for (auto j = h[u]; j; j = g[j].l) if (g[j].v != p) 
        dd[g[j].v] = dd[u] + 1, dfsd(g[j].v, u);
}

void dfs0(int u, int p)
{
    sz[u] = 1;
    for (auto j = h[u]; j; j = g[j].l) if (g[j].v != p) 
    {
        int v = g[j].v;
        dfs0(v, u);
        sz[u] += sz[v];
        if (a[v] + 1 >= a[u]) c[u] = a[u], a[u] = a[v] + 1;
        else if (a[v] + 1 >= c[u]) c[u] = a[v] + 1;
    }
}

void dfs1(int u, int p)
{
    for (auto j = h[u]; j; j = g[j].l) if (g[j].v != p)
    {
        int v = g[j].v;
        b[v] = b[u] + 1;
        if (a[v] + 1 != a[u]) b[v] = max(b[v], a[u] + 1);
        else b[v] = max(b[v], c[u] + 1);
        dfs1(v, u);
    }
}

void init()
{
    ShinLena;
    cin >> n;
    for (int u, v, i = 1; i < n; ++i) cin >> u >> v, --u, --v, add_edge(u, v), add_edge(v, u);

    dfsd(0, 0);
    int root = 0, rootdep = -1;
    for (int i = 0; i < n; ++i) if (dd[i] > rootdep) rootdep = dd[i], root = i;
    dd[root] = 0; dfsd(root, root);
    dfs0(root, root);
    dfs1(root, root);

    map<int, int> hi, lo;
    for (int i = 0; i < n; ++i)
    {
        for (auto x : {sz[i], n - sz[i] + 1})
        {
            hi[x] = max(hi[x], dd[i]);
            lo[x] = min(lo[x], dd[i]);
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        if (i&1) continue;
        ans[i] = hi[i/2] - lo[i/2] + 1;
    }
}

void answer()
{
    for (int i = 1; i <= n; ++i)
    {
        if (i&1) cout << "1\n";
        else cout << ans[i] << '\n';
    }
}

int main()
{
    init();
    answer();

    return 0;
}

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