Submission #1200729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200729		Pacybwoah	Tree (IOI24_tree)	C++20	0 / 100	2096 ms	28580 KiB

tree

#include "tree.h"
#include<iostream>
#include<algorithm>
#include<utility>
#include<map>
#include<vector>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
namespace{
    int n;
    vector<vector<int>> graph;
    vector<int> p;
    vector<ll> vec, dp;
    vector<int> ids;
    ll l, r, ans = 0;
    void dfs(int node, int parent){
        for(auto &x: graph[node]){
            if(x == parent) continue;
            dfs(x, node);
            dp[node] += dp[x];
        }
        if((int)graph[node].size() == 1){
            dp[node] = l;
            ans += l * vec[node];
        }
    }
}

void init(std::vector<int> P, std::vector<int> W) {
    n = (int)P.size();
    graph.resize(n + 1);
    vec.resize(n + 1);
    dp.resize(n + 1);
    p.resize(n + 1);
    for(int i = 1; i < n; i++){
        graph[i + 1].push_back(P[i] + 1);
        graph[P[i] + 1].push_back(i + 1);
        p[i + 1] = P[i] + 1;
    }
    p[1] = 1;
    for(int i = 1; i <= n; i++) vec[i] = W[i - 1];
    ids.resize(n + 1);
    for(int i = 1; i <= n; i++) ids[i] = i;
    auto cmp = [&](int a, int b){
        return vec[a] < vec[b];
    };
    sort(next(ids.begin()), ids.end(), cmp);
}

long long query(int L, int R) {
    l = L;
    r = R;
    fill(dp.begin(), dp.end(), 0);
    ans = 0;
    dfs(1, 0);
    for(int ord = 1; ord <= n; ord++){
        int node = ids[ord];
        ll mini = dp[node], maxi = dp[node];
        int cur = node;
        while(cur != 1){
            cur = p[cur];
            mini = min(mini, dp[cur]);
            maxi = max(maxi, dp[cur]);
        }
        if(maxi <= r) continue;
        ll sub = min(maxi - r, mini - l);
        ans += sub * vec[node];
        cur = node;
        dp[node] -= sub;
        while(cur != 1){
            cur = p[cur];
            dp[cur] -= sub;
        }
    }
    return ans;
}

• 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