Submission #1243763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243763		Gray	Tree (IOI24_tree)	C++20	23 / 100	2096 ms	49316 KiB

tree

#include "tree.h"
#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;
const ll INF = 2e9;
const ll MOD = 998244353;

int n;
vector<int> p, w;
vector<vector<int>> A;

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

pair<pair<ll, ll>, map<ll, ll>> dfs(ll u, ll l, ll r){
    map<ll, ll> rems; ll cval=0, res=0;
    if (A[u].empty()){
        return {{w[u]*l, l}, rems};
    }else{
        for (auto v:A[u]){
            auto ret = dfs(v, l, r);
            cval+=ret.ff.ss; res+=ret.ff.ff;
            for (auto [x, y]:ret.ss){
                rems[x]+=y;
            }
        }
        if (cval>r){
            while (cval>r and !rems.empty() and w[u]>(*rems.begin()).ff){
                ll con = min(cval-r, (*rems.begin()).ss);
                cval-=con; res+=con*((*rems.begin()).ff);
                if ((*rems.begin()).ss==con){
                    rems.erase(rems.begin());
                }else{
                    rems[(*rems.begin()).ff]-=con;
                }
            }
            if (cval>r){
                ll con=cval-r; cval-=con; res+=w[u]*con;
            }
        }
        rems[w[u]]+=cval-l; ll cap = cval-l;
        map<ll, ll> arems; ll csum=0;
        for (auto [x, y]:rems){
            if (csum==cap) break;
            ll add = min(y, cap-csum);
            arems[x]+=add; csum+=add;
        }
        return {{res, cval}, arems};
    }
}

long long query(int L, int R) {
    auto res = dfs(0, L, R);
    return res.ff.ff;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 0 / 18
• Subtask 4: 0 / 7
• Subtask 5: 0 / 11
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19