oj.uz

Submission #391281

# Submission time Handle Problem Language Result Execution time Memory
391281 2021-04-18T12:10:25 Z Victor Cat in a tree (BOI17_catinatree) C++17
0 / 100
 1 ms 332 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -