Submission #1294557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294557		NValchanov	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	423 ms	47240 KiB

meetings2

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

const int MAXN = 2e5 + 10;
const int MAXLOG = 18;

struct Edge
{
    int u, v;
    int cost;

    Edge(int u, int v, int cost)
    {
        this->u = u;
        this->v = v;
        this->cost = cost;
    }

    friend bool operator<(const Edge e1, const Edge e2)
    {
        return e1.cost < e2.cost;
    }
};

int n;
vector < int > adj[MAXN];
vector < Edge > edges;
int subsz[MAXN];
int sz[MAXN];
int leader[MAXN];
int fart[MAXN][2];
int lift[MAXN][MAXLOG];
int par[MAXN];
int depth[MAXN];
int ans[MAXN];
int diam;

int lca(int u, int v)
{
    if(depth[u] < depth[v])
        swap(u, v);

    int diff = depth[u] - depth[v];

    for(int j = MAXLOG - 1; j >= 0; j--)
    {
        if(diff & (1 << j))
        {
            u = lift[u][j];
        }
    }

    if(u == v)
        return u;

    for(int j = MAXLOG - 1; j >= 0; j--)
    {
        if(lift[u][j] != lift[v][j])
        {
            u = lift[u][j];
            v = lift[v][j];
        }
    }

    return lift[u][0];
}

int distance(int u, int v)
{
    int l = lca(u, v);

    return depth[u] + depth[v] - 2 * depth[l];
}

int find_leader(int u)
{
    return leader[u] == u ? u : leader[u] = find_leader(leader[u]);
}

void init()
{
    for(int i = 1; i <= n; i++)
    {
        leader[i] = i;
        sz[i] = 1;
        fart[i][0] = fart[i][1] = i;
    }
}

void unite(int u, int v)
{
    int lead_u = find_leader(u);
    int lead_v = find_leader(v);

    assert(lead_u != lead_v);

    if(sz[lead_u] < sz[lead_v])
    {
        swap(lead_u, lead_v);
        swap(u, v);
    }

    int dist0 = distance(u, fart[lead_u][0]);
    int dist1 = distance(u, fart[lead_u][1]);

    if(dist0 < dist1)
        swap(fart[lead_u][0], fart[lead_u][1]);

    dist0 = distance(v, fart[lead_v][0]);
    dist1 = distance(v, fart[lead_v][1]);

    if(dist0 < dist1)
        swap(fart[lead_v][0], fart[lead_v][1]);

    int diam_u = distance(fart[lead_u][0], fart[lead_u][1]);
    int diam_v = distance(fart[lead_v][0], fart[lead_v][1]);

    if(diam_u < diam_v)
    {
        fart[lead_u][0] = fart[lead_v][0];
        fart[lead_u][1] = fart[lead_v][1];
    }

    int opt = distance(u, fart[lead_u][0]) + distance(v, fart[lead_v][0]) + 1;

    if(max(diam_u, diam_v) < opt)
        fart[lead_u][1] = fart[lead_v][0];

    int cur_diam = distance(fart[lead_u][0], fart[lead_v][1]);

    diam = max(diam, cur_diam);

    leader[v] = u;
    sz[u] += sz[v];
}

void read()
{
    cin >> n;

    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

void dfs(int u, int p)
{
    subsz[u] = 1;
    par[u] = p;
    depth[u] = depth[p] + 1;

    for(int v : adj[u])
    {
        if(v == p)
            continue;

        dfs(v, u);

        subsz[u] += subsz[v];
    }
}

void fill_lift()
{
    for(int i = 1; i <= n; i++)
    {
        lift[i][0] = par[i];
    }

    for(int j = 1; j < MAXLOG; j++)
    {
        for(int i = 1; i <= n; i++)
        {
            lift[i][j] = lift[lift[i][j - 1]][j - 1];
        }
    }
}

void find_edges(int u, int p)
{
    for(int v : adj[u])
    {
        if(v == p)
            continue;

        find_edges(v, u);

        int cost = min(subsz[v], n - subsz[v]);

        edges.push_back(Edge(u, v, cost));
    }
}

void solve()
{
    sort(edges.begin(), edges.end());

    int ptr = edges.size() - 1;

    for(int i = (n / 2) * 2; i >= 1; i -= 2)
    {
        while(0 <= ptr && edges[ptr].cost == i / 2)
        {
            int u = edges[ptr].u;
            int v = edges[ptr].v;
            unite(u, v);

            ptr--;
        }

        ans[i] = diam + 1;
    }

    for(int i = 1; i <= n; i++)
    {
        if(i % 2 == 0)
        {
            cout << ans[i] << endl;
        }
        else
        {
            cout << 1 << endl;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    read();
    dfs(1, 1);
    fill_lift();
    init();
    find_edges(1, 1);
    solve();

    return 0;
}

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