Submission #1200723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200723		Pacybwoah	Tree (IOI24_tree)	C++20	10 / 100	2095 ms	28836 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<ll> vec, dp;
    ll l, r;
    ll dfs(int node, int parent){
        ll ans = 0;
        for(auto &x: graph[node]){
            if(x == parent) continue;
            ans += dfs(x, node);
            dp[node] += dp[x];
        }
        if(dp[node] < l){
            assert((int)graph[node].size() == 1);
            ans += vec[node] * (l - dp[node]);
            dp[node] = l;
        }
        else if(dp[node] > r){
            ans += vec[node] * (dp[node] - r);
            dp[node] = r;
        }
        return ans;
    }
}

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);
    for(int i = 1; i < n; i++){
        graph[i + 1].push_back(P[i] + 1);
        graph[P[i] + 1].push_back(i + 1);
    }
    for(int i = 1; i <= n; i++) vec[i] = W[i - 1];
}

long long query(int L, int R) {
    l = L;
    r = R;
    fill(dp.begin(), dp.end(), 0);
    return dfs(1, 0);
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 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