Submission #347207

#	Time	Username	Problem	Language	Result	Execution time	Memory
347207		AriaH	Cat in a tree (BOI17_catinatree)	C++11	100 / 100	379 ms	47468 KiB

catinatree

/** bahoone naiar **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define endl                        "\n"

const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

int n, d, dis[N], H[N];

vector < int > G[N];

set < pii > st;

void dfs(int v, int P)
{
    H[v] = H[P] + 1;
    st.insert(Mp(-H[v], v));
    for(auto u : G[v])
    {
	if(u == P) continue;
	dfs(u, v);
    }
}

int main()
{
    scanf("%d%d", &n, &d);
    for(int i = 1; i <= n; i ++)
    {
	dis[i] = 1e9;
    }
    for(int i = 1; i < n; i ++)
    {
	int x;
	scanf("%d", &x);
	G[x + 1].push_back(i + 1);
	G[i + 1].push_back(x + 1);
    }
    dfs(1, 0);
    int tot = 0;
    while(!st.empty())
    {
	int v = st.begin()->S;
	st.erase(st.begin());
	if(dis[v] < d) continue;
	/*for(int i = 1; i <= n; i ++)
	{
	    printf("%d ", dis[i]);
	}
	printf("\n");
	*/
	tot ++;
	dis[v] = 0;
	deque < int > dq;
	dq.push_back(v);
	while(!dq.empty())
	{
	    int cu = dq.front();
	    dq.pop_front();
	    for(auto u : G[cu])
	    {
		if(dis[u] > dis[cu] + 1)
		{
		    dis[u] = dis[cu] + 1;
		    if(dis[u] < d)
		    {
			dq.push_back(u);
		    }
		}
	    }
	}
    }
    printf("%d\n", tot);
    return 0;
}
/*
4 3
0
0
1
*/

Compilation message (stderr)

catinatree.cpp: In function 'int main()':
catinatree.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |     scanf("%d%d", &n, &d);
      |     ~~~~~^~~~~~~~~~~~~~~~
catinatree.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |  scanf("%d", &x);
      |  ~~~~~^~~~~~~~~~

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