Submission #389865

#	Time	Username	Problem	Language	Result	Execution time	Memory
389865		couplefire	Meetings 2 (JOI21_meetings2)	C++17	100 / 100	2139 ms	56572 KiB

meetings2

#include <bits/stdc++.h>
using namespace std;
#define MAXN 200005
#define int long long

int ckmin(int &a, int b){return (b<a)?a=b:a;}
int ckmax(int &a, int b){return (b>a)?a=b:b;}

int n;
vector<int> adj[MAXN];
int siz[MAXN];
bool vis[MAXN];
int ans[MAXN];
int tmpsiz[MAXN];
int depth[MAXN];
set<array<int, 3>, greater<>> st;

void dfs(int v, int p){
    siz[v] = 1;
    for(auto u : adj[v]){
        if(u == p || vis[u]) continue;
        dfs(u, v);
        siz[v] += siz[u];
    }
}

int centroid(int v){
    dfs(v, -1);
    int cursiz = siz[v], p = -1;
    do{
        int nxt = -1;
        for(auto u : adj[v]){
            if(u == p || vis[u]) continue;
            if(2*siz[u] > cursiz) nxt = u;
        }
        p = v, v = nxt;
    } while(~v);
    return p;
}

void dfs2(int v, int p, int d){
    depth[v] = d;
    tmpsiz[v] = 1;
    for(auto u : adj[v]){
        if(u == p || vis[u]) continue;
        dfs2(u, v, d+1);
        tmpsiz[v] += tmpsiz[u];
    }
}

void calc(int v, int p, int r, int c){
    st.insert({tmpsiz[v], depth[v], r});
    int k = 2*min(tmpsiz[v], tmpsiz[c]-tmpsiz[r]);
    ckmax(ans[k], depth[v]+1);
    for(auto u : adj[v]){
        if(u == p || vis[u]) continue;
        calc(u, v, r, c);
    }
}

void solve(int c){
    st.clear();
    dfs2(c, -1, 0);
    for(auto u : adj[c]){
        if(vis[u]) continue;
        calc(u, c, u, c);
    }
    multiset<int, greater<>> mst;
    map<int, int> mp;
    for(auto x : st){
        int s = x[0], d = x[1], r = x[2];
        if(mp[r] < d){
            if(mp[r] > 0) mst.erase(mst.find(mp[r]));
            mp[r] = d;
            mst.insert(d);
        }
        if((int)mst.size() >= 2){
            int len = (*mst.begin())+(*next(mst.begin()))+1;
            ckmax(ans[2*s], len);
        }
    }
}

void decomp(int v, int p){
    int c = centroid(v);
    solve(c);
    vis[c] = 1;
    for(auto u : adj[c]){
        if(vis[u]) continue;
        decomp(u, c);
    }
}

signed main(){
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i<n-1; i++){
        int a, b; cin >> a >> b; --a; --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i = 1; i<=n; i++) ans[i] = 1;
    decomp(0, -1);
    for(int i = n; i>=0; i--) ckmax(ans[i], ans[i+1]);
    for(int i = 1; i<=n; i++){
        if(i%2) cout << 1 << endl;
        else cout << ans[i] << endl;
    }
}

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