oj.uz

Submission #253193

# Submission time Handle Problem Language Result Execution time Memory
253193 2020-07-27T11:30:59 Z aviroop123 Cat in a tree (BOI17_catinatree) C++14
51 / 100
 17 ms 9472 KB 
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") // codeforces
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native") // yandex

#include "bits/stdc++.h"
using namespace std;
#ifndef LOCAL
#define endl '\n'
#endif

#define fr(i, a, b) for(int i = a; i <= b; i++)
#define rf(i, a, b) for(int i = a; i >= b; i--)
#define pf push_front
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
#define lb lower_bound
#define ub upper_bound

typedef long long ll;
typedef long double f80;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int pct(int x) { return __builtin_popcount(x); }
int pct(ll x) { return __builtin_popcountll(x); }
int bt(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))
int bt(ll x) { return 63 - __builtin_clzll(x); } // floor(log2(x))
int cdiv(int a, int b) { return a / b + !(a < 0 || a % b == 0); }
ll cdiv(ll a, ll b) { return a / b + !(a < 0 || a % b == 0); }
int nxt_C(int x) { int c = x & -x, r = x + c; return (((r ^ x) >> 2) / c) | r; }
ll nxt_C(ll x) { ll c = x & -x, r = x + c; return (((r ^ x) >> 2) / c) | r; }

vector<int> get_bits(int mask) {
	vector<int> bb;
	while(mask) { int b = bt(mask); bb.pb(b); mask ^= (1 << b); }
	reverse(all(bb));
	return bb;
}

int get_mask(vector<int> v) {
	int mask = 0;
	for(int x : v) { mask ^= (1 << x); }
	return mask;
}

template<typename T>
void uniq(vector<T> &v) { sort(all(v)); v.resize(unique(all(v)) - v.begin()); }

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll rand(ll l, ll r){
	uniform_int_distribution<ll> uid(l, r);
	return uid(rng);
}

void sc() {}

template <typename Head, typename... Tail>
void sc(Head &H, Tail &... T) { cin >> H; sc(T...); }

#ifdef LOCAL
#define debug(...) cerr << "[L:" << __LINE__ << "][" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// #ifndef LOCAL
// string to_string(__int128 x) {
// 	string s = "";
// 	bool neg = 0;
// 	if(x < 0) { s += "-"; neg = 1; x = -x; }
// 	if(!x) s += '0';
// 	while(x) {
// 		int rem = x % 10;
// 		s += to_string(rem);
// 		x /= 10;
// 	}
// 	reverse(s.begin() + neg, s.end());
// 	return s;
// }
// #endif

const int mod = 1e9 + 7; // 998244353;

int pwr(int a,ll b) {
	int ans = 1;
	while(b) {
		if(b & 1) ans = (ans * 1LL * a) % mod;
		a = (a * 1LL * a) % mod;
		b >>= 1;
	}
	return ans;
}

/*
	Lookout for overflows!!
	Check array sizes!!
	Clear before test cases!!
	Use the correct modulo!!
	Check for corner cases!!
	Are you forgetting something?!
	Read problem statement carefully!!!
*/

const int N = 1505;
int dp[N][N];
int sz[N];
int dp1[N];
int n, d;
vector<int> g[N];

void dfs(int u,int p) {
    sz[u] = 1;
    fr(i, 0, n) {
        dp[u][i] = 0;
    }
    dp[u][0] = 1;
    for(int v : g[u]) {
        if(v != p) {
            dfs(v, u);
            fr(i, 0, sz[u] + sz[v]) {
                dp1[i] = 0;
            }
            for(int i = 0; i <= sz[u]; i++) { // take something from u and v
                for(int j = 0; j <= sz[v]; j++) {
                    if(i + j + 1 < d) continue;
                    int k = min(i, j + 1);
                    dp1[k] = max(dp1[k], dp[u][i] + dp[v][j]);
                }
            }
            fr(i, 0, sz[v]) { // take everything from v
                dp1[i + 1] = max(dp1[i + 1], dp[v][i]);
            }
            sz[u] += sz[v];
            fr(i, 0, sz[u]) {
                dp[u][i] = max(dp[u][i], dp1[i]);
            }
        }
    }
}

void solve() {
    sc(n, d);
    fr(i, 2, n) {
        int p;
        sc(p);
        p++;
        g[i].pb(p);
        g[p].pb(i);
        debug(i, p);
    }
    dfs(1, 0);
    int ans = 0;
    fr(i, 0, n) {
        ans = max(ans, dp[1][i]);
    }
    cout << ans;
}

int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	// cin >> t;
	for(int tt = 1; tt <= t; tt++) {
		solve();
	}
	return 0;
}

Compilation message

catinatree.cpp: In function 'void solve()':
catinatree.cpp:158:20: warning: statement has no effect [-Wunused-value]
         debug(i, p);
                    ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 512 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 512 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 0 ms 512 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 512 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 0 ms 512 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 512 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 512 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 0 ms 512 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 512 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 0 ms 512 KB Output is correct
21 Correct 11 ms 9472 KB Output is correct
22 Correct 2 ms 3328 KB Output is correct
23 Correct 2 ms 3328 KB Output is correct
24 Correct 2 ms 3328 KB Output is correct
25 Correct 5 ms 6272 KB Output is correct
26 Correct 5 ms 6272 KB Output is correct
27 Correct 5 ms 6272 KB Output is correct
28 Correct 8 ms 9216 KB Output is correct
29 Correct 9 ms 9216 KB Output is correct
30 Correct 8 ms 9216 KB Output is correct
31 Correct 8 ms 9216 KB Output is correct
32 Correct 9 ms 9088 KB Output is correct
33 Correct 9 ms 9088 KB Output is correct
34 Correct 7 ms 8704 KB Output is correct
35 Correct 8 ms 8704 KB Output is correct
36 Correct 9 ms 9344 KB Output is correct
37 Correct 12 ms 9344 KB Output is correct
38 Correct 13 ms 9304 KB Output is correct
39 Correct 13 ms 9344 KB Output is correct
40 Correct 17 ms 9472 KB Output is correct

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 512 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 512 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 0 ms 512 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 0 ms 512 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 0 ms 512 KB Output is correct
21 Correct 11 ms 9472 KB Output is correct
22 Correct 2 ms 3328 KB Output is correct
23 Correct 2 ms 3328 KB Output is correct
24 Correct 2 ms 3328 KB Output is correct
25 Correct 5 ms 6272 KB Output is correct
26 Correct 5 ms 6272 KB Output is correct
27 Correct 5 ms 6272 KB Output is correct
28 Correct 8 ms 9216 KB Output is correct
29 Correct 9 ms 9216 KB Output is correct
30 Correct 8 ms 9216 KB Output is correct
31 Correct 8 ms 9216 KB Output is correct
32 Correct 9 ms 9088 KB Output is correct
33 Correct 9 ms 9088 KB Output is correct
34 Correct 7 ms 8704 KB Output is correct
35 Correct 8 ms 8704 KB Output is correct
36 Correct 9 ms 9344 KB Output is correct
37 Correct 12 ms 9344 KB Output is correct
38 Correct 13 ms 9304 KB Output is correct
39 Correct 13 ms 9344 KB Output is correct
40 Correct 17 ms 9472 KB Output is correct
41 Runtime error 3 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Halted 0 ms 0 KB -