QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#204085#4941. Tree Beautytriplem5ds#WA 66ms33160kbC++233.1kb2023-10-07 01:11:562023-10-07 01:11:56

Judging History

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

  • [2023-10-07 01:11:56]
  • 评测
  • 测评结果:WA
  • 用时:66ms
  • 内存:33160kb
  • [2023-10-07 01:11:56]
  • 提交

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];
}

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

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: 0ms
memory: 9332kb

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Wrong Answer
time: 66ms
memory: 33160kb

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:

1806039378
477606250
1432818750
672469600
4448576553
1987509504
4448576553
2912404904
4448576553
1761831250
15808754641
27348474038
10251514036
5068150941
36176702224
41573877092
35292074590
35499497590
34393241590
12426561750
30289102766
57879478219
56727445055
43122897448
94606311462
104081588299
...

result:

wrong answer 1st lines differ - expected: '1818724600', found: '1806039378'