Submission #873903

#	Time	Username	Problem	Language	Result	Execution time	Memory
873903		noiaint	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	280 ms	93580 KiB

catinatree

#include <bits/stdc++.h>
 
using namespace std;
 
#define file ""
 
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
 
#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll
 
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}
 
const int N = 2e5 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;
 
template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}
 
int n, d;
vector<int> adj[N];
 
namespace task_n2 {
 
int dis[5005], chosen[5005];
int v[5005];
 
void dfs(int u) {
    for (int v : adj[u]) if (dis[v] == -1 && !chosen[v]) {
        dis[v] = dis[u] + 1;
        dfs(v);
    }
}
 
void solve() {
    memset(dis, -1, sizeof dis);
    dis[1] = 1;
    dfs(1);
    int cur = 1;
    for (int i = 1; i <= n; ++i) if (dis[i] > dis[cur]) cur = i;
    chosen[cur] = true;
 
    int ans = 0;
 
    memset(v, 0x3f, sizeof v);
 
    while (true) {
        ++ans;
        memset(dis, -1, sizeof dis);
        dis[cur] = 0;
        dfs(cur);
        for (int i = 1; i <= n; ++i) mini(v[i], dis[i]);
        int nxt = -1;
        for (int i = 1; i <= n; ++i) if (v[i] >= d) {
            if (nxt == -1) nxt = i;
            else if (dis[i] > dis[nxt]) nxt = i;
        }
        if (nxt == -1) break;
        cur = nxt;
        chosen[cur] = true;
    }
    cout << ans;
}
 
}
 
namespace greedy {
 
int h[N], f[N];
 
void dfs(int u, int p) {
    h[u] = oo;
    for (int v : adj[u]) if (v != p) {
        dfs(v, u);
        if (h[u] + h[v] + 1 >= d) {
            f[u] += f[v];
            mini(h[u], h[v] + 1);
        }
        else {
            f[u] += f[v] - 1;
            maxi(h[u], h[v] + 1);
        }
    }
    if (h[u] >= d) {
        f[u] += 1;
        h[u] = 0;
    }
}
 
void solve() {
    dfs(1, 0); 
 
    cout << f[1];
}
 
}
 
namespace sack {
 
int h[N];
multiset<int> f[N];
 
void pre_dfs(int u, int p) {
    for (int v : adj[u]) if (v != p) {
        h[v] = h[u] + 1;
        pre_dfs(v, u);
    }
}
 
void sack(int u, int p) {
    f[u].insert(h[u]);
    for (int v : adj[u]) if (v != p) {
        sack(v, u);
        if (f[u].size() < f[u].size()) swap(f[u], f[v]);
        while (f[u].size() && f[v].size() && *f[u].begin() + *f[v].begin() - 2 * h[u] < d) {
            if (*f[u].begin() > *f[v].begin()) f[v].erase(f[v].begin());
            else f[u].erase(f[u].begin());
        }
        for (int x : f[v]) f[u].insert(x);
    }
}
 
void solve() {
    pre_dfs(1, 0);
    sack(1, 0);
    cout << (int) f[1].size();
}
 
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
 
    cin >> n >> d;
    for (int i = 2; i <= n; ++i) {
        int p;
        cin >> p;
        ++p;
        adj[i].push_back(p);
        adj[p].push_back(i);
    }
 
    // greedy::solve();
    // task_n2::solve();
    sack::solve();
 
    return 0;
}
 
/*
 
*/

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