Submission #1236362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236362		just	Tree (IOI24_tree)	C++20	10 / 100	2090 ms	12044 KiB

tree

#include "tree.h"

#include "bits/stdc++.h"
using namespace std;

#define vec vector
#define int long long
#define all(x) (x).begin(), (x).end()

const int mod = 1e9 + 7;
const int inf = 1e18;

using pii = pair<int, int>;

template<typename T>
void print(const vec<T> &a) {
    for(auto x: a) cerr << x << " ";
    cerr << endl;
}

int n;
vec<int> p, w;

void init(vec<signed> P, vec<signed> W) {
    n = P.size();
    p.resize(n);
    w.resize(n);
    
    for(int i = 0; i < n; i++) p[i] = P[i], w[i] = W[i];
}

int query(signed L, signed R) {
    int l = L, r = R;
    vec<int> sum(n, 0);
    vec<int> ans(n);
    vec<int> deg(n, 0);
    for(int i = 0; i < n; i++) if (p[i] != -1) deg[p[i]]++;
    
    queue<int> leaves;
    for (int i = 0; i < n; i++) if (deg[i] == 0) leaves.push(i);
    while (leaves.size()) {
        auto i = leaves.front();
        leaves.pop();
        if (sum[i] < l) ans[i] = l - sum[i], sum[i] = l;
        else if (sum[i] >= l && sum[i] <= r) ans[i] = 0;
        else if (sum[i] > r) ans[i] = r - sum[i], sum[i] = r;
        if (p[i] != -1) {
            sum[p[i]] += sum[i];
            deg[p[i]]--;
            if (deg[p[i]] == 0) leaves.push(p[i]);
        }
    }
    
    int cost = 0;
    for(int i = 0; i < n; i++) cost += abs(ans[i]) * w[i];
    return cost;
}

// signed main() {
//     init({-1, 0, 0}, {1, 1, 1});
//     cout << query(1, 1) << endl;
//     cout << query(1, 2) << endl;
// }

• 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