QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#344850#7305. Lowest Common AncestorIBoryWA 838ms12648kbC++172.0kb2024-03-05 15:57:522024-03-05 15:57:53

Judging History

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

  • [2024-03-05 15:57:53]
  • 评测
  • 测评结果:WA
  • 用时:838ms
  • 内存:12648kb
  • [2024-03-05 15:57:52]
  • 提交

answer

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

const int MAX = 200007, LIM = (1 << 9) - 1;
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]);
			p = P[top[p]];
		}
		return ret;
	}
} 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, 0);
		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)) == LIM) {
				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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 12648kb

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: 0
Accepted
time: 30ms
memory: 11828kb

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
11857
20427
21897
22192
26895
7096
7179
47267
48895
57515
3405
6810
16053
24241
22833
15057
30886
34491
38747
37197
23773
65304
57242
55117
66877
7183
14366
15410
16454
5758
9451
6683
11109
23015
24891
29156
35244
41332
41537
37300
51071
58569
59109
70092
93562
98559
108242
88010
120021
991...

result:

ok 181926 numbers

Test #3:

score: -100
Wrong Answer
time: 838ms
memory: 12400kb

input:

1477
3418 2604 3534 2752 131 645 5196 4830 3302 3842 1625 3740 9292 9939 1582 4155 3540 3753 7421 3629 7596 2043 1399 8955 2124 7955 6100 1346 1339 3935 767 4593 1720 3200 2248 6972 7122 9566 624 9948 6048 8338 208 8669 827 3770 4306 9503 1935 6488 454 3510 4974 2964 5407 138 5468 1142 1812 5864 803...

output:

3418
5803
9152
13820
18874
26680
33465
41014
25683
51131
42058
39772
46791
50431
71966
64478
59926
77557
63112
88734
65714
71174
94621
92142
101334
117673
92286
90454
122881
126056
126405
137417
149983
109256
150899
154398
173188
119649
166368
169452
175799
143976
216296
149549
223478
222792
195677
...

result:

wrong answer 511th numbers differ - expected: '2509778', found: '50405'