Submission #907729

#	Time	Username	Problem	Language	Result	Execution time	Memory
907729		shoryu386	Cat in a tree (BOI17_catinatree)	C++17	100 / 100	996 ms	97240 KiB

catinatree

#include <bits/stdc++.h>
using namespace std;

#define int long long

vector<int> adj[200007];

int depth[200007];
bitset<200007> marked;
void dfs(int x, int p, int d){
	depth[x] = d;
	
	for (auto y : adj[x]){
		if (y == p) continue;
		dfs(y, x, d+1);
	}
}

int dfsMarked(int x, int p){
	int ans = INT_MAX;
	if (marked[x]) return 0;
	
	for (auto y : adj[x]){
		if (y == p) continue;
		ans = min(dfsMarked(y, x) + 1, ans);
	}
	return ans;
}

int n, m; 
#define MAXN 200001
#define LOGN 20
vector<int> al[MAXN];
int dist[MAXN];
int ss[MAXN]; int lvl[MAXN];
int dfsSS(int x, int p, int l){
	ss[x] = 1;
	for (int i : al[x]){
		if (i == p || lvl[i] != -1) continue;
		
		ss[x] += dfsSS(i, x, l);
	}
	return ss[x];
}

vector<int> decomp[MAXN];

void dfsDist(int x, int p, int carry){
	dist[x] = carry;
	if (p != -1) decomp[x].push_back(p);
	for (int i : al[x]){
		if (i == p) continue;
		dfsDist(i, x, carry+1); 
	}
	return;
}

int centroidFind(int x, int p, int subtreesize){
	//cout << x << ' ' << p << ' ' << subtreesize << "\n\n\n";
	for (int i : al[x]){
		if (i == p || lvl[i] != -1) continue;
		if (ss[i] > subtreesize/2) return centroidFind(i, x, subtreesize);
	}
	return x;
}

int centPar[MAXN];
void centroidTreeCreate(int x, int p, int level){
	int stsize = dfsSS(x, p, level);
	int cent = centroidFind(x, -1, stsize);
	lvl[cent] = level;
	if (p == -1) p = cent;
	
	centPar[cent] = p;
	for (int i : al[cent]){
		if (lvl[i] == -1) centroidTreeCreate(i, cent, level+1);
	}	
}

//property: LCA between x and y on centroid tree will appear in path between x and y
//so traversing up the centroid tree from z tells us all possible paths if we treat each ancestor correctly

int kthPar(int a, int k){
	for (int x = 0; x < LOGN; x++){
		if (k & (1<<x)) a = decomp[a][x];
	}
	return a;
}

int lca(int a, int b){
	if (dist[a] > dist[b]) swap(a, b);
	
	if (dist[a] != dist[b]) b = kthPar(b, dist[b] - dist[a]);
	
	for (int x = LOGN; x > -1; x--){
		if ((int)decomp[a].size() > x && (int)decomp[b].size() > x && decomp[a][x] != decomp[b][x]){
			a = decomp[a][x]; b = decomp[b][x];
		}
	}
	if (a == b) return a;
	return decomp[a][0];
	
}

int closest[MAXN];

void update(int root, int x, int level){
	closest[x] = min(closest[x], dist[root]+dist[x]-2*dist[lca(root, x)]);
	while (level != 0){
		x = centPar[x]; level--;
		closest[x] = min(closest[x], dist[root]+dist[x]-2*dist[lca(root, x)]);
	}
}

bool red[MAXN];

int query(int root, int x, int level){
	
	int ans = closest[x];
	
	while (level != 0){
		x = centPar[x];
		ans = min(closest[x]+dist[root]+dist[x]-2*dist[lca(root, x)], ans);
		level--;
	}
	return ans;
}


main(){
	int d; cin >> n >> d;
	int p[n];
	for (int x = 1; x < n; x++){
		cin >> p[x];
		
		adj[x].push_back(p[x]);
		al[x].push_back(p[x]);
		adj[p[x]].push_back(x);
		al[p[x]].push_back(x);
	}
	
	dfs(0, -1, 0);
	
	vector<int> depthOrder[200007];
	for (int x = 0; x < n; x++){
		depthOrder[depth[x]].push_back(x);
	}
	
	memset(lvl, -1, sizeof(lvl)); for (int x = 0; x < n; x++) closest[x] = INT_MAX;
	memset(dist, -1, sizeof(dist));
	dfsDist(0, -1, 0);

	for (int x = 0; x < LOGN; x++){
		for (int y = 0; y < n; y++){
			if ((int)decomp[y].size() > x && (int)decomp[decomp[y][x]].size() > x) decomp[y].push_back(decomp[decomp[y][x]][x]);
		}
	}
	
	centroidTreeCreate(0, -1, 0);

	
	int ans = 0;
	for (int x = 200000; x > -1; x--){
		for (auto y : depthOrder[x]){
			//cout << y << ' ' << dfsMarked(y, -1) << '\n';
			
			if (query(y, y, lvl[y]) >= d){
				update(y, y, lvl[y]); red[y] = 1;
				
				marked[y] = 1;
				ans++;
			}
			
			//cout << y << ' ' << marked[y] << '\n';
		}
	}
	cout << ans;
}

Compilation message (stderr)

catinatree.cpp:130:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  130 | main(){
      | ^~~~

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