Submission #788375

#	Time	Username	Problem	Language	Result	Execution time	Memory
788375		winter0101	Meetings 2 (JOI21_meetings2)	C++14	100 / 100	448 ms	61752 KiB

meetings2

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=2e5+9;
vector<int>a[maxn],a1[maxn],a2[maxn];
//a1 add sub
//a2 reverse sub
int sub[maxn];
int rev[maxn];
int dep[maxn];
int st[maxn][19];
int in[maxn],out[maxn];
int tme=0;
int n;
void dfs(int u,int par){
sub[u]=1;
in[u]=++tme;
for(auto v:a[u]){
    if (v==par)continue;
    dep[v]=dep[u]+1;
    st[v][0]=u;
    for1(i,1,18)st[v][i]=st[st[v][i-1]][i-1];
    dfs(v,u);
    sub[u]+=sub[v];
}
rev[u]=n+1-sub[u];
out[u]=tme;
}
int lca(int u,int v){
if (dep[u]<dep[v])swap(u,v);
int k=dep[u]-dep[v];
for1(i,0,18){
if (k>>i&1)u=st[u][i];
}
if (u==v)return u;
for2(i,18,0){
if (!st[u][i]||!st[v][i])continue;
if (st[u][i]!=st[v][i]){
    u=st[u][i];
    v=st[v][i];
}
}
return st[u][0];
}
int dis(int u,int v){
return dep[u]+dep[v]-2*dep[lca(u,v)]+1;
}
int ans[maxn];
bool t1[maxn],t2[maxn];
pii newdia(const pii &p,int u){
int x=p.fi,y=p.se,z=u;
int xy=dis(x,y),yz=dis(y,z),xz=dis(x,z);
int mx=max({xy,yz,xz});
if (mx==xy)return {x,y};
if (mx==yz)return {y,z};
if (mx==xz)return {x,z};
}
int it[maxn*4];
void update(int id,int l,int r,int u,int val){
if (l>u||r<u)return;
if (l==r){
    it[id]=val;
    return;
}
int mid=(l+r)/2;
update(id*2,l,mid,u,val);
update(id*2+1,mid+1,r,u,val);
it[id]=max(it[id*2],it[id*2+1]);
}
int get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return 0;
if (u<=l&&r<=v)return it[id];
int mid=(l+r)/2;
return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n;
    for1(i,1,n-1){
    int u,v;
    cin>>u>>v;
    a[u].pb(v);
    a[v].pb(u);
    }
    dfs(1,0);
    for1(i,1,n){
    a1[sub[i]].pb(i);
    a2[rev[i]].pb(i);
    }
    int cnt=0;
    pii dia;
    for2(i,n,1){
    for (auto v:a1[i]){
        t1[v]=1;
        if (t2[v]){
            cnt++;
            //ver.pb(v);
            if (cnt==1){
                dia.fi=dia.se=v;
            }
            else {
                dia=newdia(dia,v);
            }
        }
    }
    for (auto v:a2[i]){
        t2[v]=1;
        if (t1[v]){
            cnt++;
            //ver.pb(v);
            if (cnt==1){
                dia.fi=dia.se=v;
            }
            else {
                dia=newdia(dia,v);
            }
        }
    }
    if (i*2<=n){
        if (cnt>=1)ans[i*2]=dis(dia.fi,dia.se);
        else ans[i*2]=1;
    }
    }
    for1(i,1,n)t1[i]=0;
    int nwdia=0;
    for2(i,n,1){
    for (auto v:a1[i]){
        update(1,1,n,in[v],dep[v]);
        int u=v;
        for2(i1,18,0){
        if (!st[u][i1])continue;
        if (t1[st[u][i1]]){
            u=st[u][i1];
        }
        }
        if (t1[u])nwdia=max(nwdia,dep[v]-dep[u]+2);
    }
    for (auto v:a2[i+1]){
        t1[v]=1;
        int maxdep=get(1,1,n,in[v],out[v]);
        nwdia=max(nwdia,maxdep-dep[v]+2);
    }
    if (i*2<=n){
        ans[i*2]=max(ans[i*2],nwdia);
    }
    }
    for1(i,1,n){
    if (i%2==1)cout<<1<<'\n';
    else cout<<ans[i]<<'\n';
    }
}

Compilation message (stderr)

meetings2.cpp: In function 'std::pair<int, int> newdia(const std::pair<int, int>&, int)':
meetings2.cpp:71:1: warning: control reaches end of non-void function [-Wreturn-type]
   71 | }
      | ^

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