Submission #347203

#	Time	Username	Problem	Language	Result	Execution time	Memory
347203		MahdiBahramian	Cat in a tree (BOI17_catinatree)	C++11	51 / 100	1103 ms	127196 KiB

catinatree

#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops,fast-math")
#pragma GCC target("fma,avx,avx2")
#define F first
#define S second
#define var auto
#define pb push_back
#define mp make_pair
#define ins insert
using namespace std;
typedef unsigned long long ll;
typedef unsigned int uint;
#define int uint
//#define int ll
typedef pair<int,int> pii;
const int Max = 4e5 + 10;
const int Mod = 1e9 + 7;

vector<int> N[Max];
int sub[Max];
vector<pii> D[Max];
bool hide[Max];
int ANS[Max];
int h[Max];

int pre(const int & v , const int & p)
{
	sub[v] = 1;
	for(int u : N[v]) if(!hide[u] && u != p) sub[v] += pre(u , v);
	return sub[v];
}
void DIST(const int & v , const int & d , const int & p , const int & c)
{
	D[v].pb(mp(c , d));
	for(int u : N[v]) if(!hide[u] && u != p) DIST(u , d + 1 , v , c);
}
int find_centroid(const int & v , const int &p , const int & sz)
{
	for(int u : N[v]) if(!hide[u] && u != p && 2 * sub[v] > sz) return find_centroid(u , v , sz);
	return v;
}

void centroid_tree(int v)
{
	pre(v , v);
	v = find_centroid(v , v , sub[v]);
	DIST(v , 0 , v , v);
	hide[v] = true;
	for(int u : N[v]) if(!hide[u]) centroid_tree(u);
}


void use(int v)
{
	for(pii x : D[v]) ANS[x.F] = min(ANS[x.F] , x.S);
}
int get(int v)
{
	int ans = 10000000;
	for(pii x : D[v]) if(ANS[x.F] <= 100000) ans = min(ans , x.S + ANS[x.F]);
	return ans;
}

int32_t main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n , d;cin >> n >> d;
	vector<pii> st;
	st.pb(mp(0 , 0));
	for(int i = 1 ; i < n ; i++)
	{
		int p;cin >> p;
		h[i] = h[p] + 1;
		st.pb(mp(h[i] , i));
		N[p].pb(i);
		N[i].pb(p);
	}
	//for(int i = 0 ; i < n ; i++) D[i].resize(20);
	centroid_tree(0);
	for(int i = 0 ; i < n ; i++) ANS[i] = 10000000;

	sort(st.begin() , st.end());
	reverse(st.begin() , st.end());
	int RES = 0;
	for(int i = 0; i < n ; i++)
	{
		int v = st[i].S;
		if(get(v) >= d)
		{
			RES++;
			use(v);
		}
	}
	cout << RES << '\n';
}

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