Submission #1243308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243308		Sam_arvandi	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	554 ms	27228 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define FOR(i, j, n) for (int i = j; i<= n; i++)
#define ROF(i, n, j) for (int i = n; i>= j; i--)
#define pb push_back
#define mp make_pair
#define S second
#define F first
#define IOS ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)

/*
#pragma GCC optimization("Ofast, unroll-loops")
#pragma GCC target("avx2")
#pragma GCC target("bmi")
#pragma GCC target("bmi2")
#pragma GCC target("lzcnt")
*/

const int mn = 2e5 + 5, inf = 1e9;
pii max1[mn], max2[mn];
int k[mn];
bool mark[mn];
int siz[mn], h[mn], out[mn];
vector<int> a[mn];
void dfs(int u, int par = 0)
{
        siz[u] = 1;
        if (par != 0) h[u] = h[par]+1;
        for(auto v: a[u])
        {
                if (mark[v] or v == par) continue;
                dfs(v, u);
                siz[u] += siz[v];
        }
        return;
}

int dfs2(int u, int n , int par = 0)
{
        for(auto v: a[u])
        {
                if (mark[v] or v == par or siz[v] <= n/2) continue;
                return dfs2(v, n, u);
        }
        return u;
}
vector<int> melat;
void dfs3(int u, int par, int x)
{
        k[u] = x;
        melat.pb(u);
        if (max1[siz[u]].F <= h[u])
        {
                if (max1[siz[u]].S != x) max2[siz[u]] = max1[siz[u]];
                max1[siz[u]] = mp(h[u], x);
        }
        else if (h[u] > max2[siz[u]].F and x != max1[siz[u]].S)
        {
                max2[siz[u]] = mp(h[u], x);
        }
        for(auto v: a[u])
        {
                if (mark[v] or v == par) continue;
                dfs3(v, u, x);
        }
        return;
}


void solve(int u)
{
        h[u] = 0;
        dfs(u);
        int n = siz[u];
        int cen = dfs2(u, n);
        //cout << cen << ' ' << n << endl;
        h[cen] = 0;
        dfs(cen);
        for(auto v: a[cen])
        {
                if (mark[v]) continue;
                dfs3(v, cen, v);
        }
        ROF(i, n-1, 1)
        {
                vector<pii> tmp;
                tmp.pb(max1[i]);
                tmp.pb(max2[i]);
                tmp.pb(max1[i+1]);
                tmp.pb(max2[i+1]);
                sort(tmp.begin(), tmp.end());
                max1[i] = tmp[3];
                if (tmp[2].S != max1[i].S)
                {
                        max2[i] = tmp[2];
                }
                else if (tmp[1].S != max1[i].S) max2[i] = tmp[1];
                else if (tmp[0].S != max1[i].S) max2[i] = tmp[0];
        }
        for(auto v: melat)
        {
                if (max1[siz[v]].S != k[v]) out[siz[v]] = max(out[siz[v]], h[v]+max1[siz[v]].F);
                else out[siz[v]] = max(out[siz[v]], h[v]+max2[siz[v]].F);
                if (n-siz[k[v]] >= siz[v]) out[siz[v]] = max(out[siz[v]], h[v]);
        }
        mark[cen] = 1;
        FOR(i, 1, n)
        {
                max1[i] = max2[i] = mp(-inf, 0);
        }
        for(auto v: melat)
        {
                k[v] = h[v] = siz[v] = 0;
        }
        melat.clear();

        for(auto v: a[cen])
        {
                if (!mark[v])
                {
                        solve(v);
                }
        }
        return;
}




signed main()
{
        IOS;
        int n, u, v;
        cin >> n;
        FOR(i, 1, n-1)
        {
                cin>> u >> v;
                a[u].pb(v);
                a[v].pb(u);
        }
        FOR(i, 1, n)
        {
                max1[i] = max2[i] = mp(-inf, 0);
        }
        solve(1);
        ROF(i, n, 1)
        {
                out[i] = max(out[i], out[i+1]);
        }
        FOR(i, 1, n)
        {
                if (i%2) cout << 1 << ' ';
                else cout << out[i/2]+1 << ' ';
        }
        return 0;
}

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