QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#344858 | #7305. Lowest Common Ancestor | IBory | WA | 43ms | 12276kb | C++17 | 2.0kb | 2024-03-05 16:19:28 | 2024-03-05 16:19:30 |
Judging History
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'