Submission #869075

#	Time	Username	Problem	Language	Result	Execution time	Memory
869075		azberjibiou	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	339 ms	77652 KiB

meetings2

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=200030;
const int mxM=500004;
const int MOD=998244353;
const ll INF=8e18;
typedef struct node{
    int p, m, pm, mp, pmp;
}node;
node mrg(node a, node b){
    node c;
    c.p=max(a.p, b.p);
    c.m=max(a.m, b.m);
    c.pm=max(a.p+b.m, max(a.pm, b.pm));
    c.mp=max(a.m+b.p, max(a.mp, b.mp));
    c.pmp=max(a.pm+b.p, max(a.p+b.mp, max(a.pmp, b.pmp)));
    return c;
}
node seg[8*mxN];
void upd(int idx, int s, int e, int pos, int val){
    if(s==e){
        seg[idx].p=val;
        seg[idx].m=-2*val;
        seg[idx].pm=seg[idx].mp=-val;
        seg[idx].pmp=0;
        return;
    }
    int mid=(s+e)/2;
    if(pos<=mid)    upd(2*idx, s, mid, pos, val);
    else    upd(2*idx+1, mid+1, e, pos, val);
    seg[idx]=mrg(seg[2*idx], seg[2*idx+1]);
}
int N;
vector <int> v[mxN];
int sub[mxN], dep[mxN];
vector <int> in[mxN];
int ei;
vector <int> ct[mxN];
int ans[mxN];
void input(){
    cin >> N;
    for(int i=1;i<N;i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
}
void dfs1(int now, int pre){
    sub[now]=1;
    in[now].push_back(++ei);
    for(int nxt : v[now]) if(nxt!=pre) {
        dep[nxt]=dep[now]+1;
        dfs1(nxt, now);
        sub[now]+=sub[nxt];
        in[now].push_back(++ei);
    }
}
void find_cent(){
    dfs1(1, -1);
    int now=1;
    while(true){
        bool esc=true;
        for(int nxt : v[now]){
            if(sub[nxt]<sub[now] && sub[nxt]>=(N+1)/2){
                now=nxt;
                esc=false;
                break;
            }
        }
        if(esc) break;
    }
    ei=0;
    dep[now]=0;
    for(int i=1;i<=N;i++)   in[i].clear();
    dfs1(now, -1);
    for(int i=1;i<=N;i++)   ct[sub[i]].push_back(i);
    for(int i=0;i<8*mxN;i++)    seg[i].p=seg[i].m=seg[i].pm=seg[i].mp=seg[i].pmp=-1e8;
    for(int x : in[now])    upd(1, 1, 2*N, x, dep[now]);
    //for(int i=1;i<=N;i++)   printf("dep[%d]=%d, sub[%d], in[%d]=%d\n", i, dep[i], i, sub[i], i, in[i]);
}
void solv(){
    for(int i=N;i>=1;i--){
        if(i%2){
            ans[i]=1;
            continue;
        }
        //printf("i=%d\n", i);
        for(int x : ct[i/2]) for(int y : in[x]) upd(1, 1, 2*N, y, dep[x]);
        //printf("\n");
        ans[i]=seg[1].pmp+1;
    }
}
int main()
{
    gibon
    input();
    find_cent();
    solv();
    for(int i=1;i<=N;i++)   cout << ans[i] << '\n';
}

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