Submission #1317543

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317543		spetr	Tree (IOI24_tree)	C++20	0 / 100	2096 ms	40556 KiB

tree

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll mmod = 998244353;
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>

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

long long query(int L, int R){
    ll n = tree.size();
    c.assign(n, 0);
    subs.assign(n, 0);
    
    // Pole setů. Každý set obsahuje pary {váha, id_vrcholu}.
    // Používáme vector setů, abychom mohli dělat swap.
    vector<set<pair<ll, ll>>> sets(n);

    // 1. Inicializace listů
    // Nastavíme C[i] = L pro listy. Ostatní vrcholy mají C[i] = 0.
    // Subs (S[i]) se dopočítá v bottom-up průchodu.
    for (ll i = 1; i < n; i++){
        if (tree[i].size() == 1){
            c[i] = L;
            subs[i] = L;
        }
    }

    // 2. Bottom-up průchod (od listů ke kořeni)
    for (ll i = n - 1; i >= 0; i--){
        
        // a) Vlastní váha a set
        sets[i].insert({w[i], i});
        ll current_sum = subs[i]; // Začínáme s tím, co už tam je (L pro listy, 0 jinak)

        // b) Sloučení dětí (Small-to-Large Merging)
        // Nejprve najdeme dítě s největším setem
        int biggest_child = -1;
        size_t max_size = 0;

        // První průchod dětmi: spočítat sumu a najít největší set
        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;
                }
            }
        }
        subs[i] = current_sum;

        // Pokud máme nějaké děti, prohodíme set s tím největším
        if (biggest_child != -1){
            swap(sets[i], sets[biggest_child]);
        }

        // Druhý průchod dětmi: dosypeme prvky z malých setů do toho velkého (teď už sets[i])
        for (ll child : tree[i]){
            if (child != parents[i] && child != biggest_child){
                for (auto &item : sets[child]){
                    sets[i].insert(item);
                }
                sets[child].clear(); // Uvolníme paměť (volitelné, ale dobré)
            }
        }

        // c) Snižování součtu, dokud je S[i] > R
        while (subs[i] > R){
            if (sets[i].empty()) break; // Nemělo by nastat, pokud existuje řešení

            // Vezmeme nejlevnější vrchol
            pair<ll, ll> best = *sets[i].begin();
            ll w_val = best.first;
            ll u = best.second; // Vrchol, který chceme snížit

            // VALIDACE & VÝPOČET K
            // Musíme zjistit, o kolik maximálně můžeme snížit uzel 'u', 
            // aniž bychom porušili podmínku S[v] >= L na cestě od 'u' k 'i'.
            
            ll max_decrease = subs[i] - R; // Potřebujeme snížit alespoň o tolik (resp. tolik chceme)
            
            ll curr = u;
            ll limit_on_path = 2e18; // Nekonečno
            
            // Jdeme nahoru až k aktuálnímu vrcholu 'i'
            while (true){
                // Kolik zbývá místa do L v aktuálním bodě cesty?
                limit_on_path = min(limit_on_path, subs[curr] - L);
                if (curr == i) break;
                curr = parents[curr];
            }

            // Pokud je limit 0, znamená to, že někde na cestě je uzel 'v', kde S[v] == L.
            // Tento uzel 'u' už nikdy nepůjde snížit (pro tento podstrom).
            if (limit_on_path == 0) {
                sets[i].erase(sets[i].begin()); // Odstraníme ho a zkusíme další v příštím cyklu
                continue; 
            }

            // Určíme reálné snížení
            ll k = min(max_decrease, limit_on_path);

            // Aplikujeme změnu
            c[u] -= k;
            
            // Aktualizujeme S[] hodnoty na cestě
            curr = u;
            while (true){
                subs[curr] -= k;
                if (curr == i) break;
                curr = parents[curr];
            }

            // Vrchol 'u' NEVYHAZUJEME hned, pokud jsme ho nevyčerpali úplně.
            // Vyhodí se sám v příští iteraci (pomocí limit_on_path == 0), 
            // až narazí na dno L.
        }
    }
    
    // Výpočet finální ceny
    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