Submission #347201

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

catinatree

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

vector<int> N[Max];
int sub[Max];
int dist[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 & p , const int & c)
{
	D[v].pb(mp(c , dist[v]));
	for(int u : N[v]) if(!hide[u] && u != p) {dist[u] = dist[v] + 1 ; DIST(u , 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;
	DIST(v , 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 = 100000000;
	for(pii x : D[v]) 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;
	set<pii , greater<pii>> st;
	st.ins(mp(0 , 0));
	for(int i = 1 ; i < n ; i++)
	{
		int p;cin >> p;
		h[i] = h[p] + 1;
		st.ins(mp(h[i] , i));
		N[p].pb(i);
		N[i].pb(p);
	}

	centroid_tree(0);
	for(int i = 0 ; i < n ; i++) ANS[i] = 100000000;

	int RES = 0;
	while(st.size())
	{
		int v= st.begin()->S;
		if(get(v) >= d)
		{
			RES++;
			use(v);
		}
		st.erase(st.begin());
	}
	cout << RES << '\n';
}

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