Submission #762080

#	Time	Username	Problem	Language	Result	Execution time	Memory
762080		LucaGreg	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	96 ms	41464 KiB

catinatree

 
#include <bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define ff first
#define ss second
//#define int long long int
 
const int INF = 2000000000;
const int mod = 1000000007;
 
vector<int> adj[200010];
int nivel[200010];
multiset<pair<int, int> > markeds[200010];
int n, d;
 
pair<int, int> dfs(int cur, int pai){
    nivel[cur] = nivel[pai] + 1;
    int sumMarked = 0;
    int qtdViz = 0;
    for(int i=0;i<(int)adj[cur].size();i++){
        int viz = adj[cur][i];
        if(viz==pai) continue;
        qtdViz++;
        pair<int, int> aux = dfs(viz, cur);
        sumMarked += aux.ss;
        markeds[cur].insert(aux);
    }
    /*cout<<cur<<" ";
    for(auto it=markeds[cur].begin();it!=markeds[cur].end();it++){
        cout<<(*it).ff<<" "<<(*it).ss<<" ";
    }
    cout<<"\n";*/
    if(qtdViz==0) return {nivel[cur], 1};
    if(((*markeds[cur].begin()).ff - nivel[cur])>=d) return {nivel[cur], sumMarked + 1};
    int lostMarked = 0;
    int minNivel = INF;
    for(auto it=markeds[cur].begin();it!=markeds[cur].end();it++){
        it++;
        auto proxIt = it;
        it--;
        if(proxIt==markeds[cur].end()){
            minNivel = (*it).ff;
            break;
        }
        if(((*it).ff + (*proxIt).ff - (2 * nivel[cur]))>=d){
            minNivel = (*it).ff;
            break;
        }else{
            lostMarked++;
        }
    }
    int qtdMarked = sumMarked - lostMarked;
    if((minNivel - nivel[cur])>=d){
        minNivel = nivel[cur];
        qtdMarked++;
    }
    return {minNivel, qtdMarked};
}
 
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(0);
    cin>>n>>d;
    for(int i=1;i<n;i++){
        int xi; cin>>xi;
        adj[xi].pb(i);
        adj[i].pb(xi);
    }
    cout<<dfs(0, 0).ss<<"\n";
    
    return 0;
} 

Compilation message (stderr)

catinatree.cpp:63:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   63 | main()
      | ^~~~

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