Submission #1248568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248568		qwerasdfzxcl	Tree (IOI24_tree)	C++20	0 / 100	2095 ms	40060 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n;
vector<int> adj[200200];
ll a[200200];

void init(std::vector<int> P, std::vector<int> W) {
    n = P.size();
    for (int i=1;i<n;i++) adj[P[i]+1].push_back(i+1);
    for (int i=0;i<n;i++) a[i+1] = W[i];
}

ll ofs[200200], len[200200];
priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<>> dp[200200];

void merge(int s, int v){
    ofs[s] += ofs[v];
    len[s] += len[v];

    if (dp[s].size() < dp[v].size()) swap(dp[s], dp[v]);
    while(!dp[v].empty()){
        auto p = dp[v].top(); dp[v].pop();
        dp[s].push(p);
    }
}

void dfs(int s, int L, int R){
    while(!dp[s].empty()) dp[s].pop();
    ofs[s] = 0;
    len[s] = 0;

    if (adj[s].empty()){
        ofs[s] = a[s] * L;
        return;
    }

    for (auto &v:adj[s]){
        dfs(v, L, R);
        merge(s, v);
    }

    int d = adj[s].size();

    ofs[s] += a[s] * L * (d - 1);
    
    ofs[s] -= a[s] * (R-L);
    len[s] += R-L;
    dp[s].push({a[s], R-L});
    

    while(len[s] > R-L){
        auto [dy, cnt] = dp[s].top(); dp[s].pop();

        ofs[s] += dy * cnt;
        len[s] -= cnt;
        if (len[s] >= R-L) continue;

        ofs[s] -= dy * ((R-L) - len[s]);
        len[s] = R-L;
        dp[s].push({dy, (R-L) - len[s]});
        break;
    }
}

long long query(int L, int R) {
    dfs(1, L, R);

    return ofs[1];
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 18
• Subtask 4: 0 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19