QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#344850 | #7305. Lowest Common Ancestor | IBory | WA | 838ms | 12648kb | C++17 | 2.0kb | 2024-03-05 15:57:52 | 2024-03-05 15:57:53 |
Judging History
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'