Submission #1317544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317544		spetr	Tree (IOI24_tree)	C++20	0 / 100	2097 ms	40520 KiB

tree

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define vl vector<long long>
#define vll vector<vector<long long>>

vll tree;
vl weights;
vl c;
vl parents;
vl w;
vl subs; // Aktuální součet v podstromu (S[i])

long long query(int L, int R){
    ll n = tree.size();
    c.assign(n, 0);
    subs.assign(n, 0);
    
    // Sety: {váha, id_vrcholu}. Používáme multiset, kdyby měly vrcholy stejnou váhu, 
    // ale set<pair> stačí, protože ID je unikátní.
    vector<set<pair<ll, ll>>> sets(n);

    // 1. Bottom-up průchod
    for (ll i = n - 1; i >= 0; i--){
        
        // a) Přidáme aktuální vrchol do setu kandidátů
        sets[i].insert({w[i], i});
        
        // Spočítáme aktuální S[i]. 
        // Protože začínáme s C[i]=0, je S[i] rovno součtu S dětí.
        ll current_sum = 0; 

        // b) Sloučení dětí (Small-to-Large Merging)
        int biggest_child = -1;
        size_t max_size = 0;

        // První průchod: najít nejtěžšího syna a sečíst S
        for (ll child : tree[i]){
            if (child != parents[i]){
                current_sum += subs[child];
                if (sets[child].size() > max_size){
                    max_size = sets[child].size();
                    biggest_child = child;
                }
            }
        }
        
        // Přičteme vlastní C[i] (které je zatím 0, ale pro úplnost)
        subs[i] = current_sum + c[i];

        // Swap s největším
        if (biggest_child != -1){
            swap(sets[i], sets[biggest_child]);
        }

        // Dosypání ostatních
        for (ll child : tree[i]){
            if (child != parents[i] && child != biggest_child){
                for (auto &item : sets[child]){
                    sets[i].insert(item);
                }
                sets[child].clear(); 
            }
        }

        // === FÁZE 1: Doplňování do L (pokud je součet moc malý) ===
        while (subs[i] < L) {
             if (sets[i].empty()) break; // Nemělo by nastat

             pair<ll, ll> best = *sets[i].begin();
             ll u = best.second;

             // Kolik potřebujeme přidat?
             ll need = L - subs[i];

             // Validace cesty nahoru: Můžeme přidat, aniž bychom porušili R?
             // (Tato kontrola je nutná, pokud by přidání způsobilo, že nějaký potomek přeteče přes R.
             // Většinou ale doplňujeme "díru", takže to projde. Ale formálně:)
             ll limit_on_path = 2e18; 
             ll curr = u;
             bool blocked = false;
             
             while (true){
                 // Kolik místa zbývá do R?
                 if (subs[curr] >= R) { // Už jsme na hraně nebo přes
                     blocked = true;
                     break;
                 }
                 limit_on_path = min(limit_on_path, (ll)R - subs[curr]);
                 if (curr == i) break;
                 curr = parents[curr];
             }

             if (blocked || limit_on_path == 0) {
                 sets[i].erase(sets[i].begin()); // Tento vrchol už nemůžeme zvýšit
                 continue;
             }

             ll k = min(need, limit_on_path);
             
             // Aplikace změny
             c[u] += k;
             curr = u;
             while(true){
                 subs[curr] += k;
                 if (curr == i) break;
                 curr = parents[curr];
             }
        }

        // === FÁZE 2: Ořezávání na R (pokud je součet moc velký) ===
        while (subs[i] > R){
            if (sets[i].empty()) break; 

            pair<ll, ll> best = *sets[i].begin();
            ll u = best.second;

            ll need = subs[i] - R;
            
            // Validace cesty nahoru: Můžeme ubrat, aniž bychom podtekli pod L?
            ll limit_on_path = 2e18;
            ll curr = u;
            bool blocked = false;

            while (true){
                if (subs[curr] <= L) {
                    blocked = true;
                    break;
                }
                limit_on_path = min(limit_on_path, subs[curr] - (ll)L);
                if (curr == i) break;
                curr = parents[curr];
            }

            if (blocked || limit_on_path == 0) {
                sets[i].erase(sets[i].begin()); // Tento vrchol už nemůžeme snížit
                continue;
            }

            ll k = min(need, limit_on_path);

            c[u] -= k;
            curr = u;
            while(true){
                subs[curr] -= k;
                if (curr == i) break;
                curr = parents[curr];
            }
        }
    }
    
    ll price = 0;
    for (ll i = 0; i < n; i++){
        price += w[i] * abs(c[i]);
    }
    return price;
}

void init(std::vector<int> P, std::vector<int> W){
    weights.clear();
    tree.clear();
    parents.clear();
    w.clear();
    
    for (ll i = 0; i < W.size(); i++){ weights.push_back(W[i]); }

    tree.resize(P.size());
    for (ll i = 1; i < P.size(); i++){
        tree[i].push_back(P[i]);
        tree[P[i]].push_back(i);
    }
    for (ll i = 0; i < P.size(); i++){
        parents.push_back(P[i]);
        w.push_back(W[i]);
    }
}

• 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