Submission #1205628

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205628		trandangquang	Meetings 2 (JOI21_meetings2)	C++20	100 / 100	182 ms	37468 KiB

meetings2

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

#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define bit(s, i) (((s) >> (i)) & 1)
#define ii pair <int, int>
#define fi first
#define se second
#define ll long long
#define eb emplace_back
#define pb push_back
#define __builtin_popcount __builtin_popcountll

template <class X, class Y>
    bool maximize(X &x, Y y) {
        if(x < y) {
            x = y;
            return true;
        }
        return false;
    }

template <class X, class Y>
    bool minimize(X &x, Y y) {
        if(x > y) {
            x = y;
            return true;
        }
        return false;
    }

void solve();
int32_t main() {
    #define task "test"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    int tc = 1; // cin >> tc;
    FOR(i, 1, tc){
        solve();
    }
}

const int N=2e5+5;
const int LG=18;

int n,sz[N],idx[N],up[N][LG+1],h[N],ans[N];
vector<int> adj[N];

void get_sz(int u, int p=-1){
    sz[u]=1;
    for(int v:adj[u]) if(v!=p){
        get_sz(v,u);
        sz[u]+=sz[v];
    }
}

int get_cen(int u, int p=-1){
    for(int v:adj[u]) if(v!=p){
        if(sz[v]>n/2) return get_cen(v,u);
    }
    return u;
}

void dfs(int u, int p=-1){
    sz[u]=1;
    for(int v:adj[u]) if(v!=p){
        up[v][0]=u;
        FOR(i,1,LG) up[v][i]=up[up[v][i-1]][i-1];
        h[v]=h[u]+1;

        dfs(v,u);
        sz[u]+=sz[v];
    }
}

int lca(int u, int v){
    if(h[u]<h[v]) swap(u,v);
    int d=h[u]-h[v];
    FOR(i,0,LG) if(bit(d,i)) u=up[u][i];
    if(u==v) return u;
    FORD(i,LG,0) if(up[u][i]!=up[v][i]) u=up[u][i],v=up[v][i];
    return up[u][0];
}

int dist(int u, int v){
    return h[u]+h[v]-2*h[lca(u,v)];
}

void solve() {
    cin>>n;
    FOR(i,1,n-1){
        int u,v; cin>>u>>v;
        adj[u].eb(v); adj[v].eb(u);
    }

    get_sz(1);
    int cen=get_cen(1);
    dfs(cen);

    iota(idx+1,idx+1+n,1);
    sort(idx+1,idx+1+n,[](int x, int y){return sz[x]>sz[y];});

    int u=cen,v=cen; /// u-v is diameter
    FOR(i,1,n){
        int mx=0, nu=cen, nv=cen;
        if(maximize(mx,dist(u,v))) nu=u, nv=v;
        if(maximize(mx,dist(u,idx[i]))) nu=u, nv=idx[i];
        if(maximize(mx,dist(v,idx[i]))) nu=v, nv=idx[i];

        if(i!=1) maximize(ans[sz[idx[i]]],mx+1);
        u=nu, v=nv;
    }

    ans[n/2+1]=1;
    FORD(i,n/2,1) maximize(ans[i],ans[i+1]);

    FOR(i,1,n){
        if(i&1) cout<<"1\n";
        else cout<<ans[i/2]<<'\n';
    }
}

Compilation message (stderr)

meetings2.cpp: In function 'int32_t main()':
meetings2.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
meetings2.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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