Submission #1149189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149189		Ludissey	Tree (IOI24_tree)	C++20	0 / 100	2097 ms	34344 KiB

tree

#include "tree.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

using namespace std;
int n;
vector<int> p, w;
vector<vector<int>> child;
int sum=0; 

void init(std::vector<int> P, std::vector<int> W) {
    p = P;
    w = W;
    n = (int)p.size();
    child.resize(n);
    for (int i = 1; i < n; i++)
    {
        child[p[i]].push_back(i);
    }
    
}

vector<pair<int,int>> dfs(int x, int l, int r){
    if(sz(child[x])==0){
        sum+=l*w[x];
        return {{w[x],l}};
    }
    vector<pair<int,int>> tot;
    for (auto u : child[x])
    {
        vector<pair<int,int>> cu=dfs(u,l,r);
        for (int i = 0; i < sz(cu); i++) tot.push_back(cu[i]);
    }
    int sm=0;
    for (int i = 0; i < sz(tot); i++) sm+=tot[i].second;
    sort(all(tot));
    tot.push_back({w[x],sm});
    for (int i = 0; i < sz(tot); i++) {
        int mn=min(tot[i].second-l,sm-r);
        sm-=mn;
        tot[i].second-=mn;
        sum+=mn*tot[i].first;
    }
    return tot;
}


long long query(int L, int R) {
    sum=0;
    dfs(0,L,R);    
    return sum;
}

• 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