QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133623#4941. Tree BeautyRd_rainydays#WA 82ms35124kbC++172.3kb2023-08-02 12:08:212023-08-02 12:08:24

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 12:08:24]
  • 评测
  • 测评结果:WA
  • 用时:82ms
  • 内存:35124kb
  • [2023-08-02 12:08:21]
  • 提交

answer

#include <bits/stdc++.h>

using ll = long long;
const int N = 1e5 + 5;
int n, q;

int fa[N];
std::vector<int> g[N];

#define mid ((l + r) / 2)
ll sum[N * 4], tag[N * 4];
void pushdown(int x, int l, int r) {
  if (!tag[x]) return;
  tag[x << 1] += tag[x];
  sum[x << 1] += tag[x] * (mid - l + 1);
  tag[x << 1 | 1] += tag[x];
  sum[x << 1 | 1] += tag[x] * (r - mid);
  tag[x] = 0;
}
void modify(int x, int l, int r, int tl, int tr, ll v) {
  if (tl <= l && r <= tr) {
    tag[x] += v;
    sum[x] += (r - l + 1) * v;
    return;
  }
  if (tl > r || l > tr) return;
  pushdown(x, l, r);
  modify(x << 1, l, mid, tl, tr, v);
  modify(x << 1 | 1, mid + 1, r, tl, tr, v);
  sum[x] = sum[x << 1] + sum[x << 1 | 1];
}
ll query(int x, int l, int r, int tl, int tr) {
  if (tl <= l && r <= tr) return sum[x];
  if (tl > r || l > tr) return 0;
  pushdown(x, l, r);
  return query(x << 1, l, mid, tl, tr) + query(x << 1 | 1, mid + 1, r, tl, tr);
}

ll acc[20][N];
int cnt[20][N];

int timer = 0, dfn[N], siz[N];
void dfs(int x) {
  dfn[x] = ++timer, siz[x] = 1;
  for (auto y : g[x]) dfs(y), siz[x] += siz[y];
}

int main() {
  scanf("%d%d", &n, &q);
  for (int i = 2; i <= n; i++) {
    scanf("%d", fa + i);
    g[fa[i]].push_back(i);
  }
  dfs(1);

  for (int x = 1; x <= n; x++)
    for (int i = 0, y = x; i < 20 && y; i++, y = fa[y])
      cnt[i][y]++; //, printf("%d, %d > %d\n", x, i, y);

  while (q--) {
    int opt;
    scanf("%d", &opt);

    if (opt == 1) {
      int x, y, k;
      scanf("%d%d%d", &x, &y, &k);

      if (k == 1) {
        modify(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, y);
      } else {
        for (int d = 0; d < 20; d++) {
          acc[d][x] += y;
          if ((y /= k) == 0) break;
        }
      }
    } else {
      int x;
      scanf("%d", &x);
      int y = x;
      ll ans = query(1, 1, n, dfn[x], dfn[x] + siz[x] - 1);

      ll cur[20];
      memset(cur, 0, sizeof(cur));
      for (int d = 0; d < 20; d++) {
        for (int p = d; p < 20; p++)
          cur[p - d] += acc[p][x];
        x = fa[x];
      }

      for (int d = 0; d < 20; d++) {
        ans += cur[d] * cnt[d][y];
        // printf(" > %d %d\n", cnt[d][y], cur[d]);
      }
      printf("%lld\n", ans);
    }
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 14444kb

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: 2ms
memory: 6960kb

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Wrong Answer
time: 82ms
memory: 35124kb

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'