Submission #719866

#	Time	Username	Problem	Language	Result	Execution time	Memory
719866		n0sk1ll	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	657 ms	54160 KiB

catinatree

#include <bits/stdc++.h>
 
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)
 
using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;
 
 
 
 
 
 
 
//Note to self: Check for overflow
 
graph g(200005);
int toindexhelpminus1[1284];
int dub[200005];
set<pii> active;
set<int> tinta;
 
int up[20][200005];
int tin[200005],tout[200005],koji[200005];
int VREME=0;
 
void dfs(int p, int q)
{
    dub[p]=dub[q]+1,tin[p]=++VREME,up[0][p]=max(0,q),koji[VREME]=p;
    for (auto it : g[p]) if (it!=q) dfs(it,p);
    tout[p]=VREME;
}
 
void build(int n)
{
    ff(k,1,20) ff(i,0,n) up[k][i]=up[k-1][up[k-1][i]];
}
 
bool anc(int a, int b)
{
    return tin[a]<=tin[b] && tout[a]>=tout[b];
}
 
int Lca(int a, int b)
{
    bff(k,0,20) if (!anc(up[k][a],b)) a=up[k][a];
    if (!anc(a,b)) a=up[0][a]; return a;
}
 
int dist(int a, int b)
{
    int c=Lca(a,b);
    return dub[a]+dub[b]-2*dub[c];
}
 
int find_closest(int p)
{
    auto kad=tinta.lower_bound(tin[p]);
    if (kad==tinta.end()) kad=tinta.begin();
 
    if (*kad==tin[p]) return p;
    auto posle=kad;
    auto pre=posle;
    if (kad==tinta.begin()) pre=prev(tinta.end());
    else pre=prev(kad);
 
    if (dist(p,koji[*pre]) < dist(p,koji[*posle])) return koji[*pre];
    return koji[*posle];
}
 
void kill(int p, int q, int d)
{
    active.erase({-dub[p],p});
    if (d>1) for (auto it : g[p]) if (it!=q) kill(it,p,d-1);
}
 
int main()
{
    FAST;
 
    int n,D; cin>>n>>D;
    ff(i,1,n)
    {
        int p; cin>>p;
        g[p].pb(i),g[i].pb(p);
    }
 
    int ans=0;
    dub[-1]=0;
 
    dfs(0,-1),tout[0]=VREME,build(n);
    ff(i,0,n) active.insert({-dub[i],i});
    ff(i,0,n) tinta.insert(tin[i]);
 
    while (!active.empty())
    {
        int p=active.begin()->yy;
 
        while (!active.empty())
        {
            int q=find_closest(p);
            if (dist(p,q)<D) active.erase({-dub[q],q}),tinta.erase(tin[q]);
            else break;
        }
 
        ans++;
    }
 
    cout<<ans<<"\n";
}
 
//Note to self: Check for overflow

Compilation message (stderr)

catinatree.cpp: In function 'int Lca(int, int)':
catinatree.cpp:67:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   67 |     if (!anc(a,b)) a=up[0][a]; return a;
      |     ^~
catinatree.cpp:67:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   67 |     if (!anc(a,b)) a=up[0][a]; return a;
      |                                ^~~~~~
catinatree.cpp: In function 'int main()':
catinatree.cpp:109:11: warning: array subscript -1 is below array bounds of 'int [200005]' [-Warray-bounds]
  109 |     dub[-1]=0;
      |     ~~~~~~^
catinatree.cpp:39:5: note: while referencing 'dub'
   39 | int dub[200005];
      |     ^~~

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