Submission #1236560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236560		a4n_	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	533 ms	27024 KiB

meetings2

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
#define F first
#define S second
#define endl '\n'
#define Mp make_pair
#define pb push_back
#define pf push_front
#define size(x) (ll)x.size()
#define all(x) x.begin(), x.end()
#define fuck(x) cout<<"("<<#x<<" : "<<x<<")\n"
 
const int N = 3e5 + 100, lg = 18;
const ll Mod = 1e9 + 7;
const ll inf = 1e18 + 10;
 
ll MOD(ll a, ll mod=Mod) {
    a%=mod; (a<0)&&(a+=mod); return a;
}
ll poww(ll a, ll b, ll mod=Mod) {
    ll res = 1;
    while(b > 0) {
        if(b%2 == 1) res = MOD(res * a, mod);
        b /= 2;
        a = MOD(a * a, mod);
    }
    return res;
}
 
int t, n, glb, tmp[N], mark[N], ans[N], subt[N], h[N];
pii dp[N];
vector<int> adj[N];

void init(int v, int p=0) {
    h[v] = h[p] + 1, subt[v] = 1;
    for(int u : adj[v]) {
        if(u == p || mark[u] == 1) continue;
        init(u, v);
        subt[v] += subt[u];
    }
}

int fnd(int v, int p=0) {
    for(int u : adj[v]) {
        if(u == p || mark[u] == 1) continue;
        if(subt[glb] / 2 < subt[u]) return fnd(u, v);
    }
    return v;
}

void dfs2(int v, int p) {
    // dp[subt[v]].S = max(dp[subt[v]].S, min(dp[subt[v]].F, h[v] - 1));
    // dp[subt[v]].F = max(dp[subt[v]].F, h[v] - 1);
    tmp[subt[v]] = max(tmp[subt[v]], h[v] - 1);
    for(int u : adj[v]) {
        if(u == p || mark[u] == 1) continue;
        dfs2(u, v);
    }
}

void dfs(int v, int p, int sz) {
    ans[min(sz, subt[v]) * 2] = max(ans[min(sz, subt[v]) * 2], h[v]);
    for(int u : adj[v]) {
        if(u == p || mark[u] == 1) continue;
        dfs(u, v, sz); 
    }
}

void solve(int v) {
    init(v);
    glb = v;

    v = fnd(v);
    init(v);
    fill(dp, dp + subt[v] + 2, Mp(-1e9, -1e9));
    fill(tmp, tmp + subt[v] + 2, -1e9);

    for(int u : adj[v]) {
        if(mark[u] == 1) continue;
        dfs(u, v, subt[v] - subt[u]);
        dfs2(u, v);
        
        for(int i=subt[u]; i>=0; i--) {
            tmp[i] = max(tmp[i], tmp[i+1]);
            ans[2*i] = max(ans[2*i], tmp[i] + dp[i].F + 1);
        }
        
        for(int i=subt[u]; i>=0; i--) {
            int x = dp[i+1].F;
            dp[i].F = max(dp[i].F, x);
            x = tmp[i];
            tmp[i] = 0;
            dp[i].F = max(dp[i].F, x);
        }
    }

    fill(tmp, tmp + subt[v] + 2, -1e9);
    fill(dp, dp + subt[v] + 2, Mp(-1e9, -1e9));

    reverse(all(adj[v]));

    for(int u : adj[v]) {
        if(mark[u] == 1) continue;
        dfs2(u, v);
        // dfs(u, v);
        
        for(int i=subt[u]; i>=0; i--) {
            tmp[i] = max(tmp[i], tmp[i+1]);
            ans[2*i] = max(ans[2*i], tmp[i] + dp[i].F + 1);
        }
        
        for(int i=subt[u]; i>=0; i--) {
            int x = dp[i+1].F;
            dp[i].F = max(dp[i].F, x);
            x = tmp[i];
            tmp[i] = 0;
            dp[i].F = max(dp[i].F, x);
        }
    }

    fill(tmp, tmp + subt[v] + 2, -1e9);
    fill(dp, dp + subt[v] + 2, Mp(-1e9, -1e9));

    mark[v] = 1;
    for(int u : adj[v]) {
        if(mark[u] == 1 )continue;
        solve(u);
    }
}

void work() {
    cin>>n;
    for(int v,u,i=1; i<n; i++) {
        cin>>v>>u;
        adj[v].pb(u); adj[u].pb(v);
    }

    solve(1);

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

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

void reset_work() {
    return;
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(0);
 
    // cin>>t;
    t = 1;
    while(t --) {
        work();
        reset_work();
    }
 
    return 0;
}

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