QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#351049 | #7305. Lowest Common Ancestor | IBory | WA | 100ms | 22992kb | C++17 | 2.9kb | 2024-03-11 13:36:40 | 2024-03-11 13:36:40 |
Judging History
answer
#include <bits/stdc++.h>
#define pii pair<int, int>
typedef long long ll;
using namespace std;
const int SZ = 1 << 18;
vector<int> G[SZ];
int W[SZ], H[SZ], P[SZ], Z[SZ], in[SZ], out[SZ], top[SZ], dn;
ll U[SZ << 1];
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 Seg {
ll T[SZ << 1], Z[SZ << 1];
void Push(int n) {
if (!Z[n]) return;
if (n < SZ) {
Z[n * 2] += Z[n];
Z[n * 2 + 1] += Z[n];
}
// cout << "temp " << U[n] << '\n';
T[n] += Z[n] * U[n];
Z[n] = 0;
}
void Update(int L, int R, int v, int sL = 1, int sR = SZ, int n = 1) {
Push(n);
if (R < sL || sR < L) return;
if (L <= sL && sR <= R) {
Z[n] += v;
Push(n);
return;
}
int mid = (sL + sR) >> 1;
Update(L, R, v, sL, mid, n * 2);
Update(L, R, v, mid + 1, sR, n * 2 + 1);
T[n] = T[n * 2] + T[n * 2 + 1];
}
ll Query(int L, int R, int sL = 1, int sR = SZ, int n = 1) {
Push(n);
if (R < sL || sR < L) return 0;
if (L <= sL && sR <= R) return T[n];
int mid = (sL + sR) >> 1;
return Query(L, R, sL, mid, n * 2) + Query(L, R, mid + 1, sR, n * 2 + 1);
}
void PathUpdate(int a, int b) {
while (top[a] != top[b]) {
if (H[top[a]] > H[top[b]]) swap(a, b);
Update(in[top[b]], in[b], 1);
b = P[top[b]];
}
if (H[a] > H[b]) swap(a, b);
Update(in[a], in[b], 1);
}
ll PathQuery(int a, int b) {
ll ret = 0;
while (top[a] != top[b]) {
if (H[top[a]] > H[top[b]]) swap(a, b);
ret += Query(in[top[b]], in[b]);
b = P[top[b]];
}
if (H[a] > H[b]) swap(a, b);
ret += Query(in[a], in[b]);
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);
for (int i = 1; i <= N; ++i) {
int p = in[i] + SZ - 1;
U[p] = W[i] - W[P[i]];
while (p >>= 1) U[p] = U[p * 2] + U[p * 2 + 1];
}
T.PathUpdate(1, 1);
for (int i = 2; i <= N; ++i) {
ll ans = T.PathQuery(1, i);
cout << ans << '\n';
T.PathUpdate(1, i);
}
for (int i = 1; i <= N; ++i) {
G[i].clear();
ll t = (U[in[i] + SZ - 1] ? -T.Query(in[i], in[i]) / U[in[i] + SZ - 1] : 0LL);
T.Update(in[i], in[i], t);
int p = (i + SZ - 1) * 2;
while (p >>= 1) U[p] = 0;
}
dn = 0;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 22864kb
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: 100ms
memory: 22992kb
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 50344 54792 62980 22833 50757 69625 73230 77486 97381 67307 111284 95981 101097 105616 49965 89537 19348 71235 42122 49357 9485 13454 24274 -4657 34369 6733 12243 11989 8211 21523 29021 61911 40544 93562 98559 108242 90812 12002...
result:
wrong answer 14th numbers differ - expected: '6810', found: '50344'