Submission #678986

#	Time	Username	Problem	Language	Result	Execution time	Memory
678986		Makarooni	Cat in a tree (BOI17_catinatree)	C++17	11 / 100	1096 ms	28924 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;

#define mr make_pair
#define endl '\n'
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(), v.end()
#define sz(x) (int) x.size()
//#define int long long

const int N = 2e5 + 10;
const int K = 499;

int dp[N][500], D, ps[N][500];
vector<int> g[N];
unordered_map<int, int> mp[N];
set<int> b[N];

void dfs(int v, int p){
    for(int u : g[v]){
        if(u == p)
            continue;
        dfs(u, v);
    }
    for(int d = D; d > 0; d--){
        vector<int> pr, su, V;
        pr.pb(0);
        su.pb(0);
        int x = D - d - 1;
        if(x < 0)
			continue;
		x = max(x, d - 1);
        for(int u : g[v]){
            if(u == p)
                continue;
            pr.pb(ps[u][x] + pr.back());
            V.pb(u);
        }
        reverse(all(g[v]));
        for(int u : g[v]){
            if(u == p)
                continue;
            su.pb(ps[u][x] + su.back());
        }
        reverse(all(su));
        for(int i = 0; i < sz(pr) - 1; i++){
            dp[v][d] = max(dp[v][d], pr[i] + su[i + 1] + dp[V[i]][d - 1]);
        }
    }
    dp[v][0]++;
    for(int u : g[v]){
        if(u == p)
            continue;
        dp[v][0] += ps[u][D - 1];
    }
    for(int i = D; i >= 0; i--)
    	ps[v][i] = max(ps[v][i + 1], dp[v][i]);
}

void dfs2(int v, int par){
    for(int u : g[v]){
        if(u == par)
            continue;
        dfs2(u, v);
    }
    for(int p = 499; p >= 1; p--){
    	//cout << p << endl;
    	int l = 0, r = 200001;
    	while(r - l > 1){
    		//cout << l << " " << r << endl;
		int d = (l + r) / 2;
        vector<int> pr, su, V;
        pr.pb(0);
        su.pb(0);
        int x = D - d - 1;
        if(x < 0){
        	r = d;
			continue;
		}
		x = max(x, d - 1);
        for(int u : g[v]){
            if(u == par)
                continue;
            auto it = b[u].lower_bound(x);
        	if(it == b[u].end())
        		pr.pb(pr.back());
            pr.pb(mp[u][*it] + pr.back());
            V.pb(u);
        }
        reverse(all(g[v]));
        for(int u : g[v]){
            if(u == par)
                continue;
            auto it = b[u].lower_bound(x);
        	if(it == b[u].end())
        		su.pb(su.back());
            su.pb(mp[u][*it] + su.back());
        }
        reverse(all(su));
        int ssb = 0;
        for(int i = 0; i < sz(pr) - 1; i++){
        	auto it = b[V[i]].lower_bound(d - 1);
        	if(it == b[V[i]].end())
        		continue;
			//cout << "hoora " << V[i] << " " << pr[i] << " " << su[i + 1] << " " << mp[V[i]][*it] << endl;
            ssb = max(ssb, pr[i] + su[i + 1] + mp[V[i]][*it]);
        }
        if(ssb >= p){
        	dp[v][p] = max(dp[v][p], d);
        	l = d;
		}
		else
			r = d;
		}
    }
    int ssb = 0;
    ssb++;
    for(int u : g[v]){
        if(u == par)
            continue;
        ssb += mp[u][D - 1];
    }
    dp[v][ssb] = max(dp[v][ssb], 0);
    for(int i = 499; i >= 0; i--){
    	mp[v][dp[v][i]] = max(mp[v][dp[v][i]], i);
    	b[v].insert(dp[v][i]);
    }
}

int32_t main(){
    ios_base:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n >> D;
    if(D > n){
    	cout << 1;
    	return 0;
	}
	if(D == 1){
		cout << n;
		return 0;
	}
    int p;
    for(int i = 1; i < n; i++){
        cin >> p;
        g[i].pb(p);
        g[p].pb(i);
    }
    if(D < 500){
    	dfs(0, -1);
    	cout << ps[0][0];
    }
    else{
		for(int i = 0; i < n; i++){
    		for(int j = 0; j <= K; j++)
    			dp[i][j] = -1000000000;
		}
    	dfs2(0, -1);
		//cout << "# " << dp[1][1] << endl;
		int ans = 1;
		for(int i = 1; i <= K; i++){
			if(dp[0][i] >= 0)
				ans = max(ans, i);
		}
		cout << ans;
	}
}

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