Submission #1166954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166954		rorro	Race (IOI11_race)	C++20	21 / 100	3096 ms	32064 KiB

race

#include <iostream>
#include <unordered_map>
#include <vector>

using ll = long long;
using namespace std;


const int MAXN = 2e5 + 7;

vector<pair<int, int>> graf[MAXN];

bool zablokowane[MAXN];
int rozmiarPoddrzewa[MAXN];

ll k;

void PoliczWielkoscPoddrzew(int v, int p){
    rozmiarPoddrzewa[v] = 1;
    for (auto& [s, w] : graf[v]){
        if (!zablokowane[s] && s != p){
            PoliczWielkoscPoddrzew(s, v);
            rozmiarPoddrzewa[v] += rozmiarPoddrzewa[s];
        }
    }
}

int znajdzCentorid(int v, int p, int calaWielkosc){
    int maksPoddrzewo = 0;

    for (auto& [s, w] : graf[v]){
        if (!zablokowane[s] && s != p){
            maksPoddrzewo = max(maksPoddrzewo, rozmiarPoddrzewa[s]);
            int kan = znajdzCentorid(s, v, calaWielkosc);
            if (kan != -1) return kan;
        }
        if (!zablokowane[s] && s == p){
            maksPoddrzewo = max(maksPoddrzewo, calaWielkosc - rozmiarPoddrzewa[s] + 1);
        }
    }

    if (maksPoddrzewo <= calaWielkosc / 2) return v;

    return -1;
}

vector<pair<ll, int>> odleglosci;

void policzOdleglosci(int v, int p, ll aktOdl, int g){
    odleglosci.push_back({aktOdl, g});
    for (auto& [s, w] : graf[v]){
        if (s != p && !zablokowane[s]) policzOdleglosci(s, v, aktOdl + w, g + 1);
    }
}


int centroidDecomp(int v){
    PoliczWielkoscPoddrzew(v, v);
    int centr = znajdzCentorid(v, v, rozmiarPoddrzewa[v]);

    //cout << v << ' ' << centr << '\n';
    zablokowane[centr] = 1;

    int wynik = 1e9;

    unordered_map<ll, int> bestOdl;
    bestOdl[0] = 0;

    for (auto& [s, w] : graf[centr]){
        if (!zablokowane[s]){
            odleglosci.clear();
            policzOdleglosci(s, s, w, 1);

            for (auto& [odl, gleb] : odleglosci){
                if (bestOdl.find(k - odl) != bestOdl.end()) wynik = min(wynik, gleb + bestOdl[k - odl]);
            }
            
            for (auto& [odl, gleb] : odleglosci){
                if (bestOdl.find(odl) == bestOdl.end()) bestOdl[odl] = gleb;
                else bestOdl[odl] = min(bestOdl[odl], gleb);
            }
        }
    }

    bestOdl.clear();


    for (auto& [s, w] : graf[centr]){
        if (!zablokowane[s]){
            wynik = min(wynik, centroidDecomp(s));
        }
    }

    return wynik;

}



int best_path(int N, int K, int H[][2] , int L[]){
    k = K;

    for (int i = 0; i < N - 1; i++){
        graf[H[i][0]].push_back({H[i][1], L[i]});
        graf[H[i][1]].push_back({H[i][0], L[i]});
    }

    int w = centroidDecomp(0);
    if (w == 1e9) w = -1;
    return w;


}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57