Submission #562615

#	Time	Username	Problem	Language	Result	Execution time	Memory
562615		anubhavdhar	Cat in a tree (BOI17_catinatree)	C++14	51 / 100	826 ms	12816 KiB

catinatree

#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 = 2e5 + 5;
const ll ROOTN = 640;
const ll LOGN = 18;
const ll INF = 1e18 + 1022;

int N, D, dis[MAXN], cat_cnt, mxdep[MAXN];
int dp[5][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;


	srand(time(NULL));
	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);
	}
	// dbgLine;
	if(true || D >= ROOTN){
		F0Re(i, N){
			vis[i] = false;
		}
		int TTT = (N > 1500) ? 40 : 100;
		int ans = 1;
		while(TTT--){
			ans = max(ans, solve(1 + rand() % N));
		}
		cout << ans << '\n';
		exit(0);
	}

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

	// dfs(1, -1);

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

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