Submission #987121

#	Time	Username	Problem	Language	Result	Execution time	Memory
987121		Jawad_Akbar_JJ	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	918 ms	89148 KiB

catinatree

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 2e5 + 10;
set<int> nei[N];
vector<int> dist[N], Par[N];
vector<pair<int,int>> order;
int sz[N], rts;
int Mn[N];

void dfs(int u,int p = -1,int h = 1){
	order.push_back({-h,u});
	for (int i : nei[u])
		if (i != p)
			dfs(i, u, h+1);
}

void dfs_size(int u,int p = -1){
	sz[u] = 1;
	for (int i : nei[u])
		if (i != p)
			dfs_size(i,u),sz[u] += sz[i];
}

int centroid(int u,int p = -1){
	for (int i : nei[u])
		if (i != p and rts/2 < sz[i])
			return centroid(i,u);
	return u;
}

void dfs2(int u,int root,int p = -1,int h = 0){
	Par[u].push_back(root);
	dist[u].push_back(h);

	for (int i : nei[u])
		if (i != p)
			dfs2(i, root, u, h+1);
}

void dec(int u,int Cen = 0){
	dfs_size(u);
	rts = sz[u];
	
	int cen = centroid(u);

	dfs2(cen,cen);

	for (int i : nei[cen])
		nei[i].erase(cen);

	for (int i : nei[cen])
		dec(i,cen);
}

void mark(int v){
	for (int i = 0;i<dist[v].size();i++)
		Mn[Par[v][i]] = min(Mn[Par[v][i]],dist[v][i]);
}

int query(int v){
	int ans = 1e9;
	for (int i=0;i<dist[v].size();i++)
		ans = min(ans,dist[v][i] + Mn[Par[v][i]]);
	return ans;
}

int main(){
	int n,D;
	scanf("%d%d",&n,&D);

	for (int i=2;i<=n;i++){
		int p;
		scanf("%d",&p);
		nei[p + 1].insert(i);
		nei[i].insert(p + 1);
	}

	dfs(1);
	sort(begin(order),end(order));

	dec(1);

	for (int i=1;i<=n;i++)
		Mn[i] = 1e9;

	int ans = 0;		

	for (auto [h,u] : order){
		if (query(u) < D)
			continue;
		mark(u);
		ans++;
	}

	cout<<ans<<'\n';
}

Compilation message (stderr)

catinatree.cpp: In function 'void mark(int)':
catinatree.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for (int i = 0;i<dist[v].size();i++)
      |                 ~^~~~~~~~~~~~~~~
catinatree.cpp: In function 'int query(int)':
catinatree.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for (int i=0;i<dist[v].size();i++)
      |               ~^~~~~~~~~~~~~~~
catinatree.cpp: In function 'int main()':
catinatree.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  scanf("%d%d",&n,&D);
      |  ~~~~~^~~~~~~~~~~~~~
catinatree.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   scanf("%d",&p);
      |   ~~~~~^~~~~~~~~

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