Submission #734533

#	Time	Username	Problem	Language	Result	Execution time	Memory
734533		Victor	Cat in a tree (BOI17_catinatree)	C++17	0 / 100	4 ms	4948 KiB

catinatree

// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (ll i = (a); i < (b); ++i)
#define per(i, a, b) for (ll i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) (ll)x.size()
#define pb push_back
#define mp make_pair
#define debug(x) cout<<#x<<" = "<<x<<endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef vector<pll> vpll;

const ll INF = 1'000'000'007;

vll graph[200005];
ll n,d,maxd,node;
bitset<200005> marked;

void dfs1(ll u,ll p, ll curd) {
    if(!marked[u]&&curd>maxd) node=u;
    trav(v,graph[u]) if(v!=p) dfs1(v,u,curd+1);
}

void dfs2(ll u,ll p,ll curd) {
    if(curd==d) return;
    marked[u]=1;
    trav(v,graph[u]) if(v!=p) dfs2(v,u,curd+1);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    cin>>n>>d;
    rep(i,1,n) {
        ll p;
        cin>>p;
        graph[p].pb(i);
        graph[i].pb(p);
    }

    ll ans=0;
    ll start=0;
    while(true) {
        maxd=-1;
        node=-1;
        dfs1(start,start,0);
        if(node==-1) break;

        dfs2(node,node,0);
        start=node;
        ++ans;
    }

    cout<<ans<<endl;
    return 0;
}

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