Submission #1149206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149206		Ludissey	Tree (IOI24_tree)	C++20	0 / 100	2091 ms	48336 KiB

tree

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

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

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

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


long long query(signed L, signed 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