Submission #1270679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270679		tvgk	Meetings 2 (JOI21_meetings2)	C++20	20 / 100	4097 ms	57072 KiB

meetings2

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<int, int>
const long mxN = 2e5 + 7, inf = 1e9 + 7;

int n, num, child[mxN], sz[mxN], ans[mxN], h[mxN], bot[mxN];
map<int, int> mp[mxN];
vector<ii> w[mxN], mem;
bool ers[mxN];

struct Segment
{
    int node[mxN * 4];

    void Upd(int vt, int val, int j = 1, int l = 1, int r = num)
    {
        if (r <= vt)
        {
            node[j] = max(node[j], val);
            return;
        }

        if (vt < l)
            return;

        int mid = (l + r) / 2;
        Upd(vt, val, j * 2, l, mid);
        Upd(vt, val, j * 2 + 1, mid + 1, r);
    }

    void Down(int j)
    {
        node[j * 2] = max(node[j * 2], node[j]);
        node[j * 2 + 1] = max(node[j * 2 + 1], node[j]);
        node[j] = -inf;
    }

    int Get(int vt, bool ers, int j = 1, int l = 1, int r = num)
    {
        if (l > vt || vt > r)
            return -inf;

        if (l == r)
        {
            int res = node[j];
            if (ers)
                node[j] = -inf;
            return res;
        }
        Down(j);

        int mid = (l + r) / 2;
        return max(Get(vt, ers, j * 2, l, mid), Get(vt, ers, j * 2 + 1, mid + 1, r));
    }

    void Reset(int j = 1, int l = 1, int r = num)
    {
        node[j] = -inf;
        if (l == r)
            return;

        int mid = (l + r) / 2;
        Reset(j * 2, l, mid);
        Reset(j * 2 + 1, mid + 1, r);
    }
};

Segment lazy, tree;

void Pre(int j, int par)
{
    sz[j] = 1;
    for (ii i : w[j])
    {
        if (i.fi == par)
            continue;

        Pre(i.fi, j);
        mp[i.fi][i.se] = sz[i.fi];
        mp[j][i.se] = n - sz[i.fi];
        sz[j] += sz[i.fi];
    }
}

void DFS(int j, int par)
{
    child[j] = 1;
    for (ii i : w[j])
    {
        if (i.fi == par || ers[i.fi])
            continue;

        DFS(i.fi, j);
        child[j] += child[i.fi];
    }
}

int Find(int j, int par)
{
    for (ii i : w[j])
    {
        if (i.fi == par || ers[i.fi])
            continue;

        if (child[i.fi] * 2 >= n)
            return Find(i.fi, j);
    }
    return j;
}

void Match(int j, int ed, int tmp)
{
    int val = mp[j][ed];
    ans[min(tmp, val)] = max(ans[min(tmp, val)], h[j] + 1);
    lazy.Upd(val, h[j] + 1);
    ans[val] = max(ans[val], h[j] + 1 + tree.Get(val, 0));
    mem.push_back({val, h[j]});

    for (ii i : w[j])
    {
        if (i.se == ed || ers[i.fi])
            continue;

        h[i.fi] = h[j] + 1;
        Match(i.fi, i.se, tmp);
    }
}

void Centroid(int j)
{
    DFS(j, 0);
    num = child[j];
    int root = Find(j, 0);

    lazy.Reset();
    tree.Reset();
    for (int i = 1; i <= num; i++)
        bot[i] = -inf;

    for (ii i : w[root])
    {
        if (ers[i.fi])
            continue;

        h[i.fi] = 1;
        Match(i.fi, i.se, mp[root][i.se]);

        for (ii u : mem)
        {
            tree.Upd(u.fi, u.se);
            ans[u.fi] = max(ans[u.fi], lazy.Get(u.fi, 1) + bot[u.fi]);
            bot[u.fi] = max(u.se, bot[u.fi]);
        }
        mem.clear();
    }

    for (int i = 1; i <= num; i++)
        ans[i] = max(ans[i], bot[i] + lazy.Get(i, 1));

//    cout << root << " : ";
//    for (int i = 1; i <= num; i++)
//        cout << ans[i] << " ";
//    cout << '\n';

    ers[root] = 1;
    for (ii i : w[root])
    {
        if (ers[i.fi])
            continue;

        Centroid(i.fi);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        w[u].push_back({v, i});
        w[v].push_back({u, i});
    }
    Pre(1, 0);

    Centroid(1);

    for (int i = n; i >= 1; i--)
        ans[i] = max({1, ans[i], ans[i + 1]});

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

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