Submission #985769

#	Time	Username	Problem	Language	Result	Execution time	Memory
985769		VinhLuu	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	33 ms	16464 KiB

catinatree

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
//#define int long long
//#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 2e5 + 5;
const int oo = 1e9 + 1;
const int mod = 1e9 + 7;
int block = 316;
//const ll oo = 5e18;

int n, D, f[N], ans, g[N];
vector<int> p[N];

void dfs(int u){
    if((int)p[u].size() == 0){
        f[u] = 0;
        ans++;
        return;
    }
    for(auto j : p[u]) dfs(j);

    sort(all(p[u]), [&](int x,int y){return f[x] > f[y];});
    int mi = f[p[u][0]] + 1;
    for(int i = 1; i < (int)p[u].size(); i ++){
        int j = p[u][i];
        if(mi + 1 + f[j] < D){
            ans--;
            continue;
        }
        mi = min(mi, 1 + f[j]);
    }
    if(mi >= D) ans++, f[u] = 0;
    else f[u] = mi;
//    cerr << u << " " << f[u] << " " << ans << " y\n";
}

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    #define task "v"
    if(fopen(task ".inp","r")){
        freopen(task ".inp","r",stdin);
        freopen(task ".out","w",stdout);
    }

    cin >> n >> D;
    for(int i = 1; i < n; i ++){
        int x; cin >> x;
        p[x].pb(i);
//        cerr << x << " " << i << " o\n";
    }
//    for(int i = 0; i < n; i ++) cerr << i << " " << (int)p[i].size() << " tt\n";
    dfs(0);
    cout << ans;
}

/*
7 5
0
1
2
0
3
1
*/

Compilation message (stderr)

catinatree.cpp: In function 'int main()':
catinatree.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen(task ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
catinatree.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen(task ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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