oj.uz

Submission #132499

# Submission time Handle Problem Language Result Execution time Memory
132499 2019-07-19T04:54:17 Z 조승현(#3204) Cat in a tree (BOI17_catinatree) C++14
0 / 100
 12 ms 11896 KB 
#include<cstdio>
#include<algorithm>
#include<vector>
#define SZ 262144
using namespace std;
int n, K, D[201000], Num[201000], Ed[201000], cnt, IT[SZ+SZ], Dep[201000], par[201000];
vector<int>E[201000], G[201000];
void DFS(int a, int pp) {
	int i;
	par[a] = pp;
	G[Dep[a]].push_back(a);
	Num[a] = ++cnt;
	for (auto &x : E[a]) {
		if (x == pp)continue;
		Dep[x] = Dep[a] + 1;
		DFS(x, a);
	}
	Ed[a] = cnt;
}
int Q[201000], head, tail;
void Put(int a, int d) {
	if (D[a] <= d)return;
	D[a] = d;
	Q[++tail] = a;
}
void Go(int a) {
	head = tail = 0;
	Put(a, 0);
	while (head < tail) {
		int x = Q[++head];
		for (auto &t : E[x]) {
			Put(t, D[x] + 1);
		}
	}
}
void Put(int b, int e, int x) {
	b += SZ, e += SZ;
	while (b <= e) {
		IT[b] = max(IT[b], x);
		IT[e] = max(IT[e], x);
		b = (b + 1) >> 1, e = (e - 1) >> 1;
	}
}
int Get(int a) {
	int r = -1e9;
	a += SZ;
	while (a) {
		r = max(r, IT[a]);
		a >>= 1;
	}
	return r;
}
int main() {
	int i, res = 0, a, j;
	scanf("%d%d", &n, &K);
	for (i = 1; i < n; i++) {
		scanf("%d", &a);
		E[i + 1].push_back(a + 1);
		E[a + 1].push_back(i + 1);
	}
	for (i = 1; i < SZ + SZ; i++)IT[i] = -1e9;
	DFS(1, 0);
	for (i = n - 1; i >= 0; i--) {
		for (auto &x : G[i]) {
			if (Dep[x] - Get(Num[x]) >= K) {
				a = x;
				res++;
				for (j = 0; j <= K; j++) {
					if (a) {
						Put(Num[a], Ed[a], Dep[a] - j * 2);
					}
					else break;
					a = par[a];
				}
			}
		}
	}
	printf("%d\n", res);
}

Compilation message

catinatree.cpp: In function 'void DFS(int, int)':
catinatree.cpp:9:6: warning: unused variable 'i' [-Wunused-variable]
  int i;
      ^
catinatree.cpp: In function 'int main()':
catinatree.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &K);
  ~~~~~^~~~~~~~~~~~~~~~
catinatree.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a);
   ~~~~~^~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 11896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 11896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 11896 KB Output isn't correct
2 Halted 0 ms 0 KB -