oj.uz

Submission #562600

# Submission time Handle Problem Language Result Execution time Memory
562600 2022-05-14T19:35:37 Z anubhavdhar Cat in a tree (BOI17_catinatree) C++14
0 / 100
 1 ms 340 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];
			if(dis[b] < D){
				vis[b] = true;
			}else if(dis[b] == D){
				V.pb(b);
			}
			dfs_from_end(b, V, a);
		}
	}
}

int solve(int a){
	dis[a] = 0;
	a = dfs_find_end(a);
	dis[a] = 0;
	vis[a] = true;
	// cerr << "placing at " << a << "\n";
	vi V;
	dfs_from_end(a, V);
	int ans = 1;
	for(int x : V){
		ans += solve(x);
	}
	return ans;
}

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;
		}
		cout << solve(1) << '\n';
		return 0;
	}

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

	dfs(1, -1);

 
 	cout<<cat_cnt<<'\n';
 
	return 0;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Halted 0 ms 0 KB -