Submission #1361319

#TimeUsernameProblemLanguageResultExecution timeMemory
1361319AliMark71Cat in a tree (BOI17_catinatree)C++20
100 / 100
408 ms76504 KiB
//
//  main.cpp
//  IntensiveCamp 1 2026
//
//  Created by Ali AlSalman on 27/04/2026.
//

#include <bits/stdc++.h>

//#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<bool> deleted;
    vec<array<int, 20>> bin;
    vec<int> depth;
    vec<optional<int>> data;
    G *decomposed;
    G(int n) : size(n), adj(n), deleted(n) {}
    
    void undirectedAdd(int i, int j) {
        adj[i].push_back(j);
        adj[j].push_back(i);
    }
    
    void prepdecomp() {
        sub.resize(size);
        decomposed = new G(size);
        decomposed->p.resize(size, -1);
        decomposed->data.resize(size);
    }
    
    int cn;
    vec<int> sub;
    void dfs0(int u, int p = -1) {
        cn++;
        sub[u] = 1;
        for (auto c : adj[u]) if (c != p && !deleted[c]) {
            dfs0(c, u);
            sub[u] += sub[c];
        }
    }
    int dfs1(int u, int p = -1) {
        for (auto c : adj[u]) if (c != p && !deleted[c] && sub[c] > cn / 2) {
            return dfs1(c, u);
        }
        return u;
    }

    vec<int> p;
    void decompose(int r = 0, int connect_to = -1) {
        assert(decomposed != nullptr);
        
        cn = 0;
        dfs0(r);
        int cen = dfs1(r);
        if(connect_to != -1) {
            decomposed->undirectedAdd(cen, connect_to);
            decomposed->p[cen] = connect_to;
        }
        deleted[cen] = true;
        for (auto c : adj[cen]) if (!deleted[c])
            decompose(c, cen);
    }
    
    void prepbin() {
        bin.resize(size);
        depth.resize(size);
        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;
    
    vec<int> nodes{0};
    G g(2*n);
    for (int i = 1; i < n; i++) {
        int j;
        cin>>j;
        g.undirectedAdd(i, j);
        nodes.push_back(i);
    }
    
    g.prepbin();
    sort(nodes.rbegin(), nodes.rend(), [&g](int a, int b) {
        return g.depth[a] < g.depth[b];
    });
    
    g.prepdecomp();
    g.decompose();
    
    G *d = g.decomposed;
    int taken = 0;
    for (int i = 0; i < n; i++) {
        int u = nodes[i];
        vec<int> dis;
        int j = 0;
        bool untaken = false;
        while (u != -1) {
            dis.push_back(g.dist(nodes[i], u));
            if (d->data[u].has_value())
                if (d->data[u].value() + dis.back() < D) { untaken = true; break; }
            
            u = d->p[u];
        }
        if (untaken) continue;
        taken++;
        u = nodes[i];
        while (u != -1) {
            d->data[u] = min(d->data[u].value_or(INT32_MAX), dis[j++]);
            u = d->p[u];
        }
    }
    
    cout<<taken<<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;
}

Compilation message (stderr)

catinatree.cpp:188:69: warning: missing terminating ' character
  188 | #warning SPOJ_BULLSCHEIßE__KIJETESANPAKALU__ without TESTCASES doesn't ducking make sense!
      |                                                                     ^
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...