QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#220286 | #7305. Lowest Common Ancestor | nice_try_fucker | RE | 0ms | 22764kb | C++20 | 3.6kb | 2023-10-20 02:58:05 | 2023-10-20 02:58:06 |
Judging History
answer
// Created with gribonator.py
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
#pragma GCC target("avx,tune=native")
#pragma GCC comment(linker, "/stack:200000000")
using namespace __gnu_pbds;
using namespace std;
mt19937 rng(chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count());
const int INF = 1e9 + 7, MD = 998244353, MAX = 200007, MOD = 1e9 + 7, MOD2 = MOD * MOD, LG = 17, B = 40;
const long long INFLL = 1e18 + 7;
int n, W[MAX];
vector <int> g[MAX];
int sub[MAX], up[LG][MAX], tin[MAX], tout[MAX], head[MAX], tt;
void dfs_pre(int v, int p = -1) {
sub[v] = 1;
for (auto& u : g[v]) if (u != p) {
dfs_pre(u, v);
W[u] -= W[v];
sub[v] += sub[u];
}
}
void dfs_hld(int v, int h, int p = -1) {
tin[v] = tt++, up[0][v] = p, head[v] = h;
if ((int)(g[v].size()) > 1) {
if (g[v][0] == p) swap(g[v][0], g[v].back());
for (int i = 1; i < (int)(g[v].size()); ++i) if (g[v][i] != p) {
if (sub[g[v][i]] > sub[g[v][0]]) swap(g[v][0], g[v][i]);
}
dfs_hld(g[v][0], h, v);
for (int i = 1; i < (int)(g[v].size()); ++i) if (g[v][i] != p) {
dfs_hld(g[v][i], g[v][i], v);
}
}
}
struct node {
long long s;
int w, d;
node() : s(0), w(0), d(0) {}
} t[1 << 19];
int R;
void push(int v) {
if (!t[v].d) return;
t[2 * v].s += t[2 * v].w * 1LL * t[v].d, t[2 * v].d += t[v].d;
t[2 * v + 1].s += t[2 * v + 1].w * 1LL * t[v].d, t[2 * v + 1].d += t[v].d;
t[v].d = 0;
}
void upd(int ql, int qr, int v, int nl, int nr) {
if (ql == nl && qr == nr) {
t[v].d++, t[v].s += t[v].w;
return;
}
push(v);
int nm = (nl + nr) / 2;
if (qr <= nm) upd(ql, qr, 2 * v, nl, nm);
else if (ql >= nm) upd(ql, qr, 2 * v + 1, nm, nr);
else
upd(ql, nm, 2 * v, nl, nm), upd(nm, qr, 2 * v + 1, nm, nr);
t[v].s = t[2 * v].s + t[2 * v + 1].s;
}
void upd(int l, int r) { upd(l, r, 1, 0, R); }
long long get(int ql, int qr, int v, int nl, int nr) {
if (ql == nl && qr == nr) {
push(v);
return t[v].s;
}
push(v);
int nm = (nl + nr) / 2;
if (qr <= nm) return get(ql, qr, 2 * v, nl, nm);
if (ql >= nm) return get(ql, qr, 2 * v + 1, nm, nr);
return get(ql, nm, 2 * v, nl, nm) + get(nm, qr, 2 * v + 1, nm, nr);
}
long long get(int l, int r) { return get(l, r, 1, 0, R); }
void resize(int n) {
R = 1;
while (R < n) R <<= 1;
fill(t + 1, t + 2 * R, node());
}
long long hld_get(int v) {
long long s = 0;
while (v != -1) {
s += get(tin[head[v]], tin[v] + 1);
v = up[0][head[v]];
}
return s;
}
void hld_upd(int v) {
while (v != -1) {
upd(tin[head[v]], tin[v] + 1);
v = up[0][head[v]];
}
}
void solve() {
tt = 0;
for (int i = 0; i < n; ++i) g[i].clear();
resize(n);
for (int i = 0; i < n; ++i) cin >> W[i];
for (int i = 1; i < n; ++i) {
int p; cin >> p, --p;
g[p].push_back(i), g[i].push_back(p);
}
dfs_pre(0);
dfs_hld(0, 0);
for (int i = 0; i < n; ++i) t[R + tin[i]].w = W[i];
for (int i = R - 1; i >= 1; --i) t[i].w = t[2 * i].w + t[2 * i + 1].w;
hld_upd(0);
for (int i = 1; i < n; ++i) {
cout << hld_get(i) << '\n';
hld_upd(i);
}
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
while (cin >> n) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 22764kb
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
Runtime Error
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...