Submission #910946

#	Time	Username	Problem	Language	Result	Execution time	Memory
910946		Tuanlinh123	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	984 ms	57480 KiB

meetings2

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

const ll maxn=200005;
vector <ll> A[maxn]; 
ll child[maxn], used[maxn], ans[maxn];
ll Time, tin[maxn], tout[maxn], dis[maxn];

struct SegTree
{
    ll n;
    vector <ll> St;
    SegTree(ll n): n(n) {St.assign(n*4+1, -1);}

    void update(ll i, ll Start, ll End, ll idx, ll val)
    {
        if (Start==End)
        {
            St[i]=val;
            return;
        }
        ll mid=(Start+End)/2;
        if (mid>=idx) update(i*2, Start, mid, idx, val);
        if (mid+1<=idx) update(i*2+1, mid+1, End, idx, val);
        St[i]=max(St[i*2], St[i*2+1]);
    }

    ll query(ll i, ll Start, ll End, ll l, ll r)
    {
        if (Start>r || End<l)
            return -1;
        if (Start>=l && End<=r)
            return St[i];
        ll mid=(Start+End)/2;
        if (mid<l) return query(i*2+1, mid+1, End, l, r);
        if (mid+1>r) return query(i*2, Start, mid, l, r);
        return max(query(i*2, Start, mid, l, r), query(i*2+1, mid+1, End, l, r));
    }
};

void getchild(ll u, ll pa)
{
    child[u]=1;
    for (ll v:A[u])
        if (v!=pa && !used[v])
            getchild(v, u), child[u]+=child[v];
}

ll findcen(ll u, ll pa, ll n)
{
    for (ll v:A[u])
        if (v!=pa && !used[v] && child[v]*2>n)
            return findcen(v, u, n);
    return u;
}

void getlist(ll u, ll pa, ll r, vector <pair<ll, pll>> &a)
{
    child[u]=1, tin[u]=++Time, dis[u]=dis[pa]+1;
    for (ll v:A[u])
        if (v!=pa && !used[v])
            getlist(v, u, r, a), child[u]+=child[v];
    tout[u]=Time;
    a.pb({child[u], {u, r}});
}

void solve(ll u)
{
    getchild(u, u);
    u=findcen(u, u, child[u]);
    vector <pair<ll, pll>> a; 
    Time=tin[u]=1, dis[u]=0;
    for (ll v:A[u])
        if (!used[v])
            getlist(v, u, v, a);
    sort(a.begin(), a.end(), greater<pair<ll, pll>>());
    SegTree S(Time);
    for (pair<ll, pll> i:a)
    {
        ll c=i.fi, idx=i.se.fi, r=i.se.se;
        ll Max=max(S.query(1, 1, Time, 1, tin[r]-1), S.query(1, 1, Time, tout[r]+1, Time));
        if (Max>=0) ans[c]=max(ans[c], dis[idx]+Max+1);
        ans[min(c, Time-child[r])]=max(ans[min(c, Time-child[r])], dis[idx]+1);
        S.update(1, 1, Time, tin[idx], dis[idx]);
    }
    used[u]=1;
    for (ll v:A[u])
        if (!used[v])
            solve(v);
}   

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n; cin >> n;
    for (ll i=1; i<n; i++)
    {
        ll u, v; cin >> u >> v;
        A[u].pb(v); A[v].pb(u);
    }
    solve(1);
    for (ll i=n; i>=1; i--)
        ans[i]=max(ans[i+1], ans[i]);
    for (ll i=1; i<=n; i++)
    {
        if (i%2==1) cout << "1\n";
        else cout << max(1ll, ans[i/2]) << "\n";
    }
}

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