fork download
copy 
  1. #include <queue>
  2. #include <vector>
  3. #include <iostream>
  4. #include <functional>
  5. using namespace std;
  6. int solve(int N, int K, vector<int> S, vector<int> V) {
  7. 	int bits = 1;
  8. 	while ((1 << bits) <= N) ++bits;
  9. 	vector<vector<int> > P(bits, vector<int>(N));
  10. 	vector<int> depth(N);
  11. 	vector<vector<int> > G(N);
  12. 	for (int i = 1; i < N; ++i) {
  13. 		P[0][i] = S[i - 1];
  14. 		depth[i] = depth[P[0][i]] + 1;
  15. 		G[P[0][i]].push_back(i);
  16. 	}
  17. 	vector<bool> coin(N);
  18. 	for (int i = 0; i < K; ++i) {
  19. 		coin[V[i]] = true;
  20. 	}
  21. 	for (int i = 1; i < bits; ++i) {
  22. 		for (int j = 0; j < N; ++j) {
  23. 			P[i][j] = P[i - 1][P[i - 1][j]];
  24. 		}
  25. 	}
  26. 	int cnt = 0;
  27. 	vector<int> sl(N), sr(N), ord;
  28. 	function<void(int)> eulertour = [&](int pos) {
  29. 		ord.push_back(pos);
  30. 		sl[pos] = cnt++;
  31. 		for (int i : G[pos]) {
  32. 			eulertour(i);
  33. 		}
  34. 		sr[pos] = cnt;
  35. 	};
  36. 	function<int(int, int)> ancestor = [&](int pos, int level) {
  37. 		for (int i = bits - 1; i >= 0; --i) {
  38. 			if (level >= (1 << i)) {
  39. 				pos = P[i][pos];
  40. 				level -= (1 << i);
  41. 			}
  42. 		}
  43. 		return pos;
  44. 	};
  45. 	eulertour(0);
  46. 	if (coin[0]) return 1;
  47. 	int L = 0, R = N + 1;
  48. 	while (R - L > 1) {
  49. 		int M = (L + R) >> 1;
  50. 		vector<vector<int> > query(N);
  51. 		for (int i = 1; i < N; ++i) {
  52. 			if (!coin[i]) continue;
  53. 			int pos = ancestor(i, (depth[i] - 1) / 2);
  54. 			query[sl[pos]].push_back(sr[pos]);
  55. 		}
  56. 		priority_queue<int, vector<int>, greater<int> > que;
  57. 		bool ok = true;
  58. 		for (int i = 0; i < N && ok; ++i) {
  59. 			for (int j : query[i]) {
  60. 				que.push(j);
  61. 			}
  62. 			if (depth[ord[i]] >= M && !que.empty()) {
  63. 				int u = que.top(); que.pop();
  64. 				if (u <= i) ok = false;
  65. 			}
  66. 		}
  67. 		if (!que.empty()) ok = false;
  68. 		if (ok) L = M;
  69. 		else R = M;
  70. 	}
  71. 	return R;
  72. }
  73. int main() {
  74. 	cin.tie(0);
  75. 	ios_base::sync_with_stdio(false);
  76. 	int N, K;
  77. 	cin >> N >> K;
  78. 	vector<int> S(N - 1);
  79. 	for (int i = 0; i < N - 1; ++i) {
  80. 		cin >> S[i]; --S[i];
  81. 	}
  82. 	vector<int> V(K);
  83. 	for (int i = 0; i < K; ++i) {
  84. 		cin >> V[i]; --V[i];
  85. 	}
  86. 	int ans = solve(N, K, S, V);
  87. 	cout << ans << '\n';
  88. 	return 0;
  89. }
Time limit exceeded #stdin #stdout 5s 3671040KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kLyVOX
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!