QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#344858#7305. Lowest Common AncestorIBoryWA 43ms12276kbC++172.0kb2024-03-05 16:19:282024-03-05 16:19:30

Judging History

你现在查看的是最新测评结果

  • [2024-03-05 16:19:30]
  • 评测
  • 测评结果:WA
  • 用时:43ms
  • 内存:12276kb
  • [2024-03-05 16:19:28]
  • 提交

answer

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int MAX = 200007, LIM = 3;
vector<int> G[MAX];
int W[MAX], H[MAX], P[MAX], Z[MAX], in[MAX], out[MAX], top[MAX], dn;
int S[MAX];

int DFS(int cur, int prev) {
	H[cur] = H[prev] + 1;
	P[cur] = prev;
	int& ret = Z[cur] = 1;
	for (int& next : G[cur]) {
		ret += DFS(next, cur);
		if (Z[next] > Z[G[cur][0]]) swap(next, G[cur][0]);
	}
	return ret;
}

void DFS2(int cur) {
	in[cur] = ++dn;
	for (int next : G[cur]) {
		top[next] = (next == G[cur][0] ? top[cur] : next);
		DFS2(next);
	}
	out[cur] = dn;
}

int LCA(int a, int b) {
	while (top[a] != top[b]) {
		if (H[top[a]] > H[top[b]]) swap(a, b);
		b = P[top[b]];
	}
	return (in[a] < in[b] ? a : b);
}

struct BIT {
	ll T[MAX];
	void Clear(int i) {
		for (; i < MAX; i += i & -i) T[i] = 0;
	}
	void Update(int i, ll v) {
		for (; i < MAX; i += i & -i) T[i] += v;
	}
	ll Query(int L, int R) {
		ll ret = 0; L--;
		for (; R; R -= R & -R) ret += T[R];
		for (; L; L -= L & -L) ret -= T[L];
		return ret;
	}
	ll PathQuery(int p) {
		ll ret = 0;
		while (p) {
			ret += Query(in[top[p]], in[p]);
			if (p == 1) return ret;
			p = P[top[p]];
		}
	}
} T;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N;
	while (cin >> N, !cin.eof()) {
		for (int i = 1; i <= N; ++i) cin >> W[i];
		for (int i = 2; i <= N; ++i) {
			int p;
			cin >> p;
			G[p].push_back(i);
		}

		DFS(1, 1);
		top[1] = 1;
		DFS2(1);

		int lastUpdate = 0;
		for (int i = 1; i <= N; ++i) {
			ll ans = T.PathQuery(i);
			for (int j = lastUpdate + 1; j < i; ++j) ans += W[LCA(i, j)];
			if (1 < i) cout << ans << '\n';

			if (i % LIM == 0) {
				for (int j = N; j > 0; --j) {
					if (lastUpdate < j && j <= i) S[j]++;
					for (int next : G[j]) S[j] += S[next];
					for (int next : G[j]) T.Update(in[next], W[j] * (S[j] - S[next]));
				}
				memset(S, 0, (N + 1) * 4);
				lastUpdate = i;
			}
		}

		for (int i = 1; i <= N; ++i) {
			G[i].clear();
			T.Clear(i);
		}
		dn = 0;
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 12276kb

input:

3
1 2 3
1 1
5
1 2 3 4 5
1 2 2 1

output:

1
2
1
3
5
4

result:

ok 6 numbers

Test #2:

score: -100
Wrong Answer
time: 43ms
memory: 12064kb

input:

13
887 4555 8570 5485 8611 9500 295 2499 83 4959 9772 8620 3825
4 4 1 3 7 12 2 1 9 5 8 12
16
3405 9213 9243 8188 2733 1333 1614 4907 4256 7506 4228 1286 6121 6155 4082 8084
1 12 9 4 2 13 3 8 9 7 11 15 8 1 10
5
7183 1481 9468 8242 1044
1 5 5 1
3
5758 3693 1694
1 2
20
6683 4426 5616 8166 810 4265 3000...

output:

887
6372
887
14942
16412
10927
13426
3548
1857
25327
20685
23820
3405
6810
16053
24241
19428
10215
21072
25979
30235
16057
17343
10215
47428
18379
58365
7183
14366
14366
15410
5758
9451
6683
11109
6683
24891
29156
29156
35244
41332
29156
37485
44983
32553
49409
26732
13366
18363
50345
13366
48088
73...

result:

wrong answer 3rd numbers differ - expected: '11857', found: '887'