oj.uz

Submission #562603

# Submission time Handle Problem Language Result Execution time Memory
562603 2022-05-14T20:03:01 Z anubhavdhar Cat in a tree (BOI17_catinatree) C++14
51 / 100
 16 ms 9300 KB 
#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first 
#define ss second
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define FOR(i,N) for(i=0;i<(N);++i)
#define FORe(i,N) for(i=1;i<=(N);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,N) for(i=(N);i>=0;--i)
#define F0R(i,N) for(int i=0;i<(N);++i)
#define F0Re(i,N) for(int i=1;i<=(N);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,N) for(int i=(N);i>=0;--i)
#define all(v) (v).begin(),(v).end()
#define dbgLine cerr<<" LINE : "<<__LINE__<<"\n"
#define ldd long double
 
using namespace std;
 
const int Alp = 26;
const int __PRECISION = 9;
const int inf = 1e9 + 8;
 
const ldd PI = acos(-1);
const ldd EPS = 1e-7;

const ll MOD = 1e9 + 7;
const ll MAXN = 1507;//2e5 + 5;
const ll ROOTN = 640;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;

int N, D, dis[MAXN], cat_cnt, mxdep[MAXN], dp[MAXN][MAXN];
bool vis[MAXN];
vi g[MAXN];

void dfs(int a, int par)
{
	for(int b : g[a])
		if(b != par)
			dfs(b, a), dp[a][0] += dp[b][D-1];

	F0Rrev(i, D-1)
	{
		if(i == 0)
			break;
		int x = i;
		int y = max(i, D-i), sm = 0, mx = 0;
		for(int b : g[a])
			if(b != par)
				sm += dp[b][y-1], mx = max(dp[b][x-1] - dp[b][y-1], mx);
		dp[a][i] = sm + mx;
		if(i < D-1)
			dp[a][i] = max(dp[a][i], dp[a][i+1]);
	}

	dp[a][0] = max(dp[a][0], dp[a][1]);

	F0R(i, D)
	{
		// cout<<"dp["<<a-1<<"]["<<i<<"] = "<<dp[a][i]<<'\n';
		cat_cnt = max(cat_cnt, dp[a][i]);
	}
}

int dfs_find_end(int a, int p = -1){
	int ans = a;
	for(int b : g[a]){
		if(b != p && !vis[b]){
			dis[b] = 1 + dis[a];
			int t = dfs_find_end(b, a);
			if(dis[t] > dis[ans]){
				ans = t;
			}
		}
	}
	return ans;
}

void dfs_from_end(int a, vector<int>& V, int p = -1){
	for(int b : g[a]){
		if(b != p && !vis[b]){
			dis[b] = 1 + dis[a];
			cerr << "dis[" << b << "] = " << dis[b] << '\n';
			if(dis[b] < D){
				vis[b] = true;
				cerr << "blocking " << b << '\n';
			}else if(dis[b] == D){
				V.pb(b);
			}
			dfs_from_end(b, V, a);
		}
	}
}

int dfs_mxdep(int a, int p = -1){
	int t = a;
	for(int b : g[a]){
		if(b != p){
			dis[b] = dis[a] + 1;
			int y = dfs_mxdep(b, a);
			if(dis[t] < dis[y]){
				t = y;
			}
		}
	}
	mxdep[a] = dis[t];
	return t;
}

int cnt;
int dfs_cnt(int a, int p = -1, int dis = D + 1){
	for(int b : g[a]){
		if(b != p){
			dis = min(dis, 1 + dfs_cnt(b, a, dis + 1));
		}
	}
	if(dis >= D){
		// cerr << "dis for " << a << " is " << dis << "\n";
		++cnt;
		dis = 0;
	}
	return dis;
}

int solve(int a){
	dis[a] = 0;
	dfs_mxdep(a);
	F0Re(i, N){
		sort(all(g[i]), [&](int a, int b){return mxdep[a] > mxdep[b];});
	}
	cnt = 0;
	dfs_cnt(a);
	return cnt;
}

signed main()
{

	/*
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	*/

	cin>>N>>D;



	cat_cnt = 1;

	F0Re(i, N)
		dis[i] = inf, mxdep[i] = 0;

	F0Re(i, N)
		F0R(j, D)
			dp[i][j] = (j==0) ? 1 : 0;

	F0Re(i, N-1)
	{
		int j;
		cin>>j;
		g[i+1].pb(j+1);
		g[j+1].pb(i+1);
	}

	if(D >= N)
	{
		cout<<"1\n";
		exit(0);
	}
	if(D == 1)
	{
		cout<<N<<'\n';
		exit(0);
	}
	if(true || D >= ROOTN){
		F0Re(i, N){
			vis[i] = false;
		}
		int TTT = 100;
		int ans = 1;
		while(TTT--){
			ans = max(ans, solve(1 + rand() % N));
		}
		cout << ans << '\n';
		// return 0;
	}

	// F0Re(i, N)
	//	sort(all(g[i]), cmp);

	dfs(1, -1);

 
	// cerr << cat_cnt << '\n';
 
	return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 16 ms 9300 KB Output is correct
22 Correct 1 ms 2260 KB Output is correct
23 Correct 3 ms 2388 KB Output is correct
24 Correct 3 ms 2388 KB Output is correct
25 Correct 2 ms 4308 KB Output is correct
26 Correct 5 ms 4412 KB Output is correct
27 Correct 6 ms 4436 KB Output is correct
28 Correct 9 ms 6488 KB Output is correct
29 Correct 9 ms 6356 KB Output is correct
30 Correct 9 ms 6500 KB Output is correct
31 Correct 9 ms 6652 KB Output is correct
32 Correct 7 ms 6228 KB Output is correct
33 Correct 8 ms 6356 KB Output is correct
34 Correct 6 ms 5972 KB Output is correct
35 Correct 6 ms 5972 KB Output is correct
36 Correct 7 ms 6484 KB Output is correct
37 Correct 7 ms 6356 KB Output is correct
38 Correct 8 ms 6740 KB Output is correct
39 Correct 11 ms 6876 KB Output is correct
40 Correct 6 ms 6564 KB Output is correct

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 16 ms 9300 KB Output is correct
22 Correct 1 ms 2260 KB Output is correct
23 Correct 3 ms 2388 KB Output is correct
24 Correct 3 ms 2388 KB Output is correct
25 Correct 2 ms 4308 KB Output is correct
26 Correct 5 ms 4412 KB Output is correct
27 Correct 6 ms 4436 KB Output is correct
28 Correct 9 ms 6488 KB Output is correct
29 Correct 9 ms 6356 KB Output is correct
30 Correct 9 ms 6500 KB Output is correct
31 Correct 9 ms 6652 KB Output is correct
32 Correct 7 ms 6228 KB Output is correct
33 Correct 8 ms 6356 KB Output is correct
34 Correct 6 ms 5972 KB Output is correct
35 Correct 6 ms 5972 KB Output is correct
36 Correct 7 ms 6484 KB Output is correct
37 Correct 7 ms 6356 KB Output is correct
38 Correct 8 ms 6740 KB Output is correct
39 Correct 11 ms 6876 KB Output is correct
40 Correct 6 ms 6564 KB Output is correct
41 Runtime error 1 ms 468 KB Execution killed with signal 11
42 Halted 0 ms 0 KB -