제출 #391281

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
391281		Victor	Cat in a tree (BOI17_catinatree)	C++17	0 / 100	1 ms	332 KiB

catinatree

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;++i)
#define per(i,a,b) for(int i=b-1;i>=a;--i)
#define trav(x,a) for(auto&x:a)
typedef pair<int,int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

vi graph[1501];
bitset<1501>rem;
int maxd,node,d;

void dfs(int u,int dist){
    if(!rem[u]&&maxd<dist++){
        node=u;
        maxd=dist;
    }
    trav(v,graph[u])dfs(v,dist);
}

void mark(int u,int dist){
    if(dist++==d)return;
    rem[u]=1;
    trav(v,graph[u])mark(v,dist);
}

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

    int n,p;
    cin>>n>>d;
    if(1500<n)return 0;
    
    rep(i,1,n){
        cin>>p;
        graph[p].push_back(i);
    }

    rep(i,0,n){
        maxd=-1;
        dfs(0,0);
        maxd=-1;
        dfs(node,0);
        if(maxd==-1){
            cout<<i<<endl;
            break;
        }
        mark(node,0);
    }
    return 0;
}

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