QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#133964#4941. Tree Beautydzy521WA 35ms37100kbC++233.2kb2023-08-02 18:55:182023-08-02 18:55:19

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 18:55:19]
  • 评测
  • 测评结果:WA
  • 用时:35ms
  • 内存:37100kb
  • [2023-08-02 18:55:18]
  • 提交

answer

#define _CRT_SEstartE_NO_DEPRECATE
#pragma warning(disable : 4996)
#include <map>
#include <unordered_map>
#include <set>
#include <fstream>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <bits/stdc++.h>
#define ACcode ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
const ll maxn = 1e5 + 7;
const ll maxm = 1e7 + 5e6 + 7;
constexpr ll mod = 1e9 + 7;
const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int Prime = 100007;
const double eps = 1e-5;
const double pi = acos(-1.0);
using namespace std;

struct BIT
{
    ll tree1[maxn], tree2[maxn];
    int n;
    ll lowbit(ll x)
    {
        return x & (-x);
    }
    void addone(int x, ll y)
    {
        ll z = x * y;
        for (; x < maxn; x += lowbit(x))
            tree1[x] += y, tree2[x] += z;
    }
    void addall(int l, int r, ll y)
    {
        addone(l, y);
        addone(r + 1, -y);
    }
    ll getpre(int x)
    {
        ll ans = 0, tx = x + 1;
        for (; x; x -= lowbit(x))
            ans += tx * tree1[x] - tree2[x];
        return ans;
    }
    ll query(int l, int r)
    {
        return getpre(r) - getpre(l - 1);
    }
} bit;
vector<int> g[maxn];
int fat[maxn], in[maxn], out[maxn], dfn;
ll tag[maxn][25], soncnt[maxn][25];
void dfs(int u, int fa)
{
    fat[u] = fa;
    soncnt[u][0] = 1;
    in[u] = ++dfn;
    for (auto v : g[u])
    {
        if (v == fa)
            continue;
        dfs(v, u);
        for (int i = 1; i <= 20; i++)
            soncnt[u][i] += soncnt[v][i - 1];
    }
    out[u] = dfn;
}
void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 2; i <= n; i++)
    {
        int x;
        cin >> x;
        g[i].push_back(x);
        g[x].push_back(i);
    }
    dfs(1, 0);
    for (int i = 1; i <= m; i++)
    {
        int ope, u, y, k;
        cin >> ope >> u;
        if (ope == 1)
        {
            cin >> y >> k;
            if (k == 1)
            {
                bit.addall(in[u], out[u], y);
                continue;
            }
            ll res = 0;
            for (int i = 0; i <= 20; i++)
            {
                res += soncnt[u][i] * y;
                tag[u][i] += y, y /= k;
            }
            bit.addall(in[u], in[u], res);
        }
        else
        {
            ll ans = bit.query(in[u], out[u]);
            int nowu = fat[u];
            for (int i = 1; i <= 20; i++)
            {
                if (nowu == 0)
                    break;
                for (int j = 1; j <= 20 - i; j++)
                    ans += tag[nowu][j] * soncnt[u][j - 1];
                nowu = fat[nowu];
            }
            cout << ans << '\n';
        }
    }
}

signed main()
{
    ACcode;
    // freopen("house.in", "r", stdin);
    // freopen("house.out", "w", stdout);
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

详细

Test #1:

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

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

input:

1 1

2 1

output:

0

result:

ok single line: '0'

Test #3:

score: -100
Wrong Answer
time: 35ms
memory: 37100kb

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
1998392724
2920352548
2782801948
2920352548
2920352548
7518672977
11295020015
7561824792
4394065144
19265994535
22947288874
15221147536
15428570536
14322314536
9119623396
12974730744
26872020588
25039643385
22398749036
27928613202
31553495219
745...

result:

wrong answer 6th lines differ - expected: '1987509504', found: '1998392724'