Submission #239829

#	Time	Username	Problem	Language	Result	Execution time	Memory
239829		dsjong	Cat in a tree (BOI17_catinatree)	C++14	11 / 100	1093 ms	16896 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;
vector<int>adj[200005];
int dis[2000][2000];
int src;
void dfs(int x, int p){
	for(int y:adj[x]){
		if(y==p) continue;
		dis[src][y]=dis[src][x]+1;
		dfs(y, x);
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, d;
	cin>>n>>d;
	for(int i=1;i<n;i++){
		int x;
		cin>>x;
		adj[x].push_back(i);
		adj[i].push_back(x);
	}
	for(int i=0;i<n;i++){
		src=i;
		dis[i][i]=0;
		dfs(i, -1);
	}
	int ans=1;
	for(int i=0;i<(1<<n);i++){
		vector<int>v;
		for(int j=0;j<n;j++){
			if(i&(1<<j)){
				v.push_back(j);
			}
		}
		bool b=true;
		for(int i=0;i<v.size();i++){
			for(int j=i+1;j<v.size();j++){
				if(dis[v[i]][v[j]]<d){
					//cout<<v[i]<<" "<<v[j]<<" "<<dis[v[i]][v[j]]<<endl;
					b=false;
				}
			}
		}
		if(b) ans=max(ans, (int)(v.size()));
	}
	cout<<ans;
}

Compilation message (stderr)

catinatree.cpp: In function 'int main()':
catinatree.cpp:39:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<v.size();i++){
               ~^~~~~~~~~
catinatree.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=i+1;j<v.size();j++){
                  ~^~~~~~~~~

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