Submission #1307106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307106		StefanSebez	Cat in a tree (BOI17_catinatree)	C++20	100 / 100	344 ms	38308 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=2e5+50,lg=18,inf=1e9;
vector<int>E[N];
int n,D;
bool deleted[N];
int depth[N],par[N][lg+1];
void DFS1(int u,int p=0,int d=0){
    depth[u]=d;par[u][0]=p;
    for(int i=1;i<=lg;i++)par[u][i]=par[par[u][i-1]][i-1];
    for(auto i:E[u])if(i!=p)DFS1(i,u,d+1);
}
int LCA(int u,int v){
    if(depth[u]<depth[v])swap(u,v);
    for(int i=lg;i>=0;i--)if(depth[par[u][i]]>=depth[v])u=par[u][i];if(u==v)return u;
    for(int i=lg;i>=0;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];return par[u][0];
}
int Dist(int u,int v){return depth[u]+depth[v]-2*depth[LCA(u,v)];}
int sajz[N],pr[N],mndist[N];bool was[N];
void DFScalc(int u,int p=0){
    sajz[u]=1;
    for(auto i:E[u])if(i!=p&&!was[i])DFScalc(i,u),sajz[u]+=sajz[i];
}
int DFSC(int u,int prvi,int p=0){
    for(auto i:E[u])if(!was[i]&&i!=p&&2*sajz[i]>=sajz[prvi])return DFSC(i,prvi,u);
    return u;
}
int CD(int u){
    DFScalc(u);
    u=DFSC(u,u);
    was[u]=true;
    for(auto i:E[u])if(!was[i])pr[CD(i)]=u;
    return u;
}
void Update(int u){
    for(int v=u;v;v=pr[v])mndist[v]=min(mndist[v],Dist(u,v));
}
int Get(int u){
    int res=inf;
    for(int v=u;v;v=pr[v])res=min(res,Dist(u,v)+mndist[v]);
    return res;
}
int main(){
    scanf("%i%i",&n,&D);
    for(int v=2;v<=n;v++){
        int u;scanf("%i",&u);u++;
        E[u].pb(v),E[v].pb(u);
    }
    int res=0;
    DFS1(1);
    int ind[n+10];iota(ind+1,ind+n+1,1);
    sort(ind+1,ind+n+1,[&](int i,int j){return depth[i]>depth[j];});
    CD(1);for(int i=1;i<=n;i++)mndist[i]=inf;
    for(int i=1;i<=n;i++)if(Get(ind[i])>=D)res++,Update(ind[i]);
    printf("%i\n",res);
    return 0;
}

Compilation message (stderr)

catinatree.cpp: In function 'int main()':
catinatree.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%i%i",&n,&D);
      |     ~~~~~^~~~~~~~~~~~~~
catinatree.cpp:52:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         int u;scanf("%i",&u);u++;
      |               ~~~~~^~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 49 / 49