QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#133540 | #4941. Tree Beauty | salvator_noster# | WA | 48ms | 22300kb | C++14 | 2.3kb | 2023-08-02 10:50:07 | 2023-08-02 10:50:37 |
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 + node[i].lazy;
}else {
node[i].sum += v;
node[i].lazy += v;
}
}
ll segment_query(int i, int l, int r, int ql, int qr) {
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);
if (mid < qr) res += segment_query(i << 1 | 1, mid + 1, r, ql, qr);
return res;
}else {
return node[i].sum;
}
}
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 > 0; 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: 7980kb
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: 5796kb
input:
1 1 2 1
output:
0
result:
ok single line: '0'
Test #3:
score: -100
Wrong Answer
time: 48ms
memory: 22300kb
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:
1146255 1146255 1146255 0 2146453 182605 2146453 1153032 2146453 2146453 3748414 5131793 1642639 1068951 5278306 7035950 4817365 4817365 4817365 25477487 15963694 9961903 7749333 7405021 13755364 11010482 0 7626527 8099811 6445290 0 25002082 164454 1068951 7131073 6535995 164454 12632913 37 19439931...
result:
wrong answer 1st lines differ - expected: '1818724600', found: '1146255'