QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133549 | #4941. Tree Beauty | salvator_noster# | WA | 49ms | 22340kb | C++14 | 2.4kb | 2023-08-02 11:00:15 | 2023-08-02 11:00:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 100000 + 5;
const int lim = 17;
int N, Q, cnt[MAX_N][20], fa[MAX_N], son[MAX_N], bro[MAX_N], dfsn[MAX_N][2], Tm;
struct SegmentNode{
ll sum, lazy;
}node[1 << 18];
ll f[MAX_N][20], val_in[MAX_N];
void segment_modify(int i, int l, int r, int ql, int qr, int v) {
if (l < ql || r > qr) {
int mid = l + r >> 1;
if (ql <= mid) segment_modify(i << 1, l, mid, ql, qr, v);
if (mid < qr) segment_modify(i << 1 | 1, mid + 1, r, ql, qr, v);
node[i].sum = node[i << 1].sum + node[i << 1 | 1].sum + (r - l + 1ll) * node[i].lazy;
}else {
node[i].sum += (r - l + 1ll) * v;
node[i].lazy += v;
}
}
ll segment_query(int i, int l, int r, int ql, int qr, ll v = 0) {
if (l < ql || r > qr) {
ll res = 0;
int mid = l + r >> 1;
if (ql <= mid) res = segment_query(i << 1, l, mid, ql, qr, v + node[i].lazy);
if (mid < qr) res += segment_query(i << 1 | 1, mid + 1, r, ql, qr, v + node[i].lazy);
return res;
}else {
return node[i].sum + v * (r - l + 1);
}
}
void dfs_init(int u) {
dfsn[u][0] = ++ Tm;
cnt[u][0] = 1;
for (int v = son[u]; v; v = bro[v]) {
dfs_init(v);
for (int i = 1; i <= lim; i ++) cnt[u][i] += cnt[v][i - 1];
}
dfsn[u][1] = Tm;
}
void modify(int x, int y, int k) {
if (k == 1) {
segment_modify(1, 1, N, dfsn[x][0], dfsn[x][1], y);
return ;
}
for (int i = 0, d = y; d; i ++, d /= k) {
f[x][i] += d;
val_in[x] += 1ll * d * cnt[x][i];
}
}
ll query(int x) {
ll res = val_in[x] + segment_query(1, 1, N, dfsn[x][0], dfsn[x][1]);
for (int i = 1, u = fa[x]; u && i <= lim; i ++, u = fa[u]) {
for (int j = 0; j + i <= lim; j ++) {
res += f[u][i + j] * cnt[x][j];
}
}
return res;
}
int main() {
scanf("%d%d", &N, &Q);
for (int i = 2; i <= N; i ++) {
scanf("%d", fa + i);
bro[i] = son[fa[i]];
son[fa[i]] = i;
}
dfs_init(1);
while (Q --) {
int ty, x, y, k;
scanf("%d%d", &ty, &x);
if (ty == 1) {
scanf("%d%d", &y, &k);
modify(x, y, k);
}else {
printf("%lld\n", query(x));
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 7844kb
input:
5 5 1 1 3 3 1 1 99 2 2 1 2 3 1 3 2 3 2 3
output:
245 97 99
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3852kb
input:
1 1 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: -100
Wrong Answer
time: 49ms
memory: 22340kb
input:
100000 100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
1818724600 1818724600 1818724600 672469600 2897885600 1987509504 2897885600 2760335000 2897885600 2897885600 7403713200 11137131600 7514202655 4383229800 19100548501 22773583200 15090370500 15297793500 14191537500 9074946248 12902639283 26557008900 24837132600 22267972000 27726020850 31286228647 745...
result:
wrong answer 5th lines differ - expected: '2920352548', found: '2897885600'