Submission #970273

#	Time	Username	Problem	Language	Result	Execution time	Memory
970273		Thanhs	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	332 ms	21584 KiB

meetings2

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
 
// #define int long long
#define pb push_back
 
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x,y) x=min((x),(y))
#define setmax(x,y) x=max((x),(y))
#define fi first
#define se second
 
// mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
// int rand(int l,int r){return l+((hdp()%(r-l+1))+r-l+1)%(r-l+1);}
 
const int N = 2e5+5;
const int mod = 998244353;
const int SQ = 450;
 
vector<int> g[N];
int n,k,ans[N],a1[N],a2[N],sz[N],mx;
bool b[N];
 
int dfs(int u,int p=0)
{
    sz[u]=1;
    for(auto v:g[u]) if(v!=p&&!b[v]) sz[u]+=dfs(v,u);
    return sz[u];
}
 
int find(int u,int s,int p=0)
{
    for(auto v:g[u]) if(!b[v]&&v!=p&&sz[v]*2>s) return find(v,s,u);
    return u;
}
 
void add(int u,int p,int l=2)
{
    setmax(a2[sz[u]],l);
    for(auto v:g[u]) if(!b[v]&&v!=p) add(v,u,l+1);
}
 
void solve(int u)
{
    u=find(u,dfs(u));
    dfs(u);
    for(int i=1;i<=sz[u];i++) a1[i]=1;
    for(auto v:g[u]) if(!b[v]) 
    {
        add(v,u);
        int cur=0;
        for(int i=sz[v];i>=1;i--)
        {
            setmax(cur,a2[i]);
            setmax(ans[2*i],cur+a1[i]-1);
        }
        cur=0;
        for(int i=sz[v];i>=1;i--)
        {
            setmax(cur,a2[i]);
            a2[i]=0;
            setmax(a1[i],cur);
        }
    }
    b[u]=1;
    for(auto v:g[u]) if(!b[v]) solve(v);
}
 
signed main()
{
    fastIO
    cin>>n;
    for(int i=1;i<=n;i++) ans[i]=1;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    solve(1);
    for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
}

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