제출 #1360996

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1360996		AliMark71	Cat in a tree (BOI17_catinatree)	C++20	11 / 100	1095 ms	580 KiB

catinatree

//
//  main.cpp
//  IntensiveCamp 1 2026
//
//  Created by Ali AlSalman on 27/04/2026.
//

#include <bits/stdc++.h>

#pragma GCC target("popcnt")

//#define INTERACTIVE
//#define TESTCASES
//#define SPOJ_BULLSCHEI__SZ__E__KIJETESANPAKALU__

#ifndef INTERACTIVE
#define endl '\n'
#endif

template<typename T>
using vec = std::vector<T>;
using namespace std;

struct G {
private:
    void dfs(int u) {
        for (auto c : adj[u]) if (c != bin[u][0]) {
            depth[c] = depth[u] + 1;
            bin[c][0] = u;
            dfs(c);
        }
    }
public:
    int size;
    vec<vec<int>> adj;
    vec<array<int, 20>> bin;
    vec<int> depth;
    G(int n) : size(n), adj(n), bin(n), depth(n) {}
    
    void undirectedAdd(int i, int j) {
        adj[i].push_back(j);
        adj[j].push_back(i);
    }
    
    void prep() {
        for (int i = 0; i < size; i++) fill(bin[i].begin(), bin[i].end(), -1);
        dfs(0);
        for (int k = 1; k < 20; k++) for (int i = 0; i < size; i++) if (bin[i][k - 1] != -1)
            bin[i][k] = bin[bin[i][k - 1]][k - 1];
    }
    
    void raise(int &u, int k) {
        if (k == 0) return;
        assert(k <= depth[u]);
        for (int i = 19; 0 <= i; i--) if ((k>>i)&1)
            u = bin[u][i];
    }
    
    int lcm(int u, int v) {
        if (depth[u] > depth[v]) swap(u, v);
        int diff = depth[v] - depth[u];
        raise(v, diff);
        if (u == v) return u;
        
        for (int i = 19; 0 <= i; i--) {
            set s{bin[u][i], bin[v][i]};
            if (s.size() == 2 && *s.begin() != -1) {
                u = bin[u][i];
                v = bin[v][i];
            }
        }
            
        assert(bin[u][0] == bin[v][0]);
        return bin[u][0];
    }
    
    int dist(int u, int v) {
        int l = lcm(u, v);
        return depth[u] + depth[v] - 2 * depth[l];
    }
};

void solve() {
    int n, d;
    cin>>n>>d;
  
    G g(n);
    for (int i = 1; i < n; i++) {
        int u;
        cin>>u;
        g.undirectedAdd(i, u);
    }
    
    g.prep();
    int ans = 1;
    for (int mask = 1; mask < (1<<g.size); mask++) if (ans < __builtin_popcount(mask)){
        bool validMask = true;
        for (int i = 0; validMask && i < g.size; i++) if ((mask>>i)&1)
            for (int j = i + 1; validMask && j < g.size; j++) if ((mask>>j)&1)
                validMask &= (g.dist(i, j) >= d);
        if (validMask) ans = __builtin_popcount(mask);
    }

    cout<<ans<<endl;
}

int main() {
#ifndef INTERACTIVE
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#endif
    
    int t = 1;
#ifdef TESTCASES
    cin>>t;
#endif
    
    for (int i = t; i--;) {
#if defined(TESTCASES) && defined(SPOJ_BULLSCHEI__SZ__E__KIJETESANPAKALU__)
        cout<<"Case "<<t-i<<":\n";
#elif defined(SPOJ_BULLSCHEI__SZ__E__KIJETESANPAKALU__)
#warning SPOJ_BULLSCHEIßE__KIJETESANPAKALU__ without TESTCASES doesn't ducking make sense!
#endif
        solve();
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

catinatree.cpp:121:69: warning: missing terminating ' character
  121 | #warning SPOJ_BULLSCHEIßE__KIJETESANPAKALU__ without TESTCASES doesn't ducking make sense!
      |                                                                     ^

• 서브태스크 1: 11 / 11
• 서브태스크 2: 0 / 40
• 서브태스크 3: 0 / 49