QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#204088#4941. Tree Beautytriplem5ds#WA 47ms33192kbC++233.1kb2023-10-07 01:15:192023-10-07 01:15:20

Judging History

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

  • [2023-10-07 01:15:20]
  • 评测
  • 测评结果:WA
  • 用时:47ms
  • 内存:33192kb
  • [2023-10-07 01:15:19]
  • 提交

answer

/// Msaa el 5ra
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include "bits/stdc++.h"

using namespace std;

#define pb push_back
#define F first
#define S second
#define f(i, a, b)  for(int i = a; i < b; i++)
#define all(a)  a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(x) (int)(x).size()
#define mp(x, y) make_pair(x,y)
#define popCnt(x) (__builtin_popcountll(x))
#define int ll

using ll = long long;
using ii = pair<int, int>;
using ull = unsigned long long;

const int N = 1e5 + 5, LG = 18, MOD = (119 << 23) + 1;
const long double PI = acos(-1);
const long double EPS = 1e-7;

int n, q;
vector<int> adj[N];
int in[N], out[N], dfsTimer;
ll t[N << 2], lz[N << 2];

void push(int node, int s, int e) {
    t[node] += lz[node] * (e - s + 1);
    if (s != e) {
        lz[node << 1] += lz[node];
        lz[node << 1 | 1] += lz[node];
    }
    lz[node] = 0;
}

void pull(int node) {
    t[node] = t[node << 1] + t[node << 1 | 1];
}

void update(int node, int s, int e, int l, int r, ll val) {
    push(node, s, e);
    if (r < s || e < l)return;
    if (l <= s && e <= r) {
        lz[node] += val;
        push(node, s, e);
        return;
    }
    int md = (s + e) >> 1;
    update(node << 1, s, md, l, r, val);
    update(node << 1 | 1, md + 1, e, l, r, val);
    pull(node);
}

int query(int node, int s, int e, int l, int r) {
    push(node, s, e);
    if (r < s || e < l)return 0;
    if (l <= s && e <= r)return t[node];
    int md = (s + e) >> 1;
    return query(node << 1, s, md, l, r)
           + query(node << 1 | 1, md + 1, e, l, r);
}

ll sum[N][20];

void dfs(int node) {
    in[node] = ++dfsTimer;
    sum[node][0] = 1;
    for (auto v: adj[node]) {
        dfs(v);
        f(i, 1, 20)sum[node][i] += sum[v][i - 1];
    }
    out[node] = dfsTimer;
}

int cnt[N][20];
int par[N];

void doWork() {
    cin >> n >> q;
    f(i, 2, n + 1) {
        int p;
        par[i] = p;
        cin >> p;
        adj[p].push_back(i);
    }
    dfs(1);
    while (q--) {
        int tp, x;
        cin >> tp >> x;
        if (tp == 1) {
            int y, k;
            cin >> y >> k;
            if (k == 1)update(1, 1, n, in[x], out[x], y);
            else {
                ll tot = 0;
                f(p, 0, 20) {
                    tot += y * sum[x][p];
                    cnt[x][p] += y;
                    y /= k;
                }
                update(1, 1, n, in[x], in[x], tot);
            }
        } else {
            ll ans = query(1, 1, n, in[x], out[x]);
            int cur = x;
            f(p, 1, 20) {
                cur = par[cur];
                f(i, 0, 20 - p) {
                    ans += cnt[cur][i + p] * sum[x][i];
                }
            }
            cout << ans << '\n';
        }

    }
}

int32_t main() {
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif // ONLINE_JUDGE
    int t = 1;
//    cin >> t;
    while (t--) {
        doWork();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9884kb

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: 8352kb

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Wrong Answer
time: 47ms
memory: 33192kb

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
2920352548
1987509504
2920352548
2782801948
2920352548
2920352548
7518672977
11295020015
7543062544
4383229800
19258702398
22947288874
15221147536
15428570536
14322314536
9119623396
12969783379
26872020588
25039643385
22398749036
27923029652
31534374661
745...

result:

wrong answer 1947th lines differ - expected: '65486449', found: '65427597'