Submission #1166948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166948		SzymonKrzywda	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

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

using ll = long long;
using namespace std;


const ll MAXN = 2e5 + 7;

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

bool zablokowane[MAXN];
ll rozmiarPoddrzewa[MAXN];

ll k;

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

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

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

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

    return -1;
}

vector<pair<ll, ll>> odleglosci;

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


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

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

    ll wynik = 1e9;

    unordered_map<ll, ll> 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);
            }
        }
    }


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

    return wynik;

}



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

    for (ll 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]});
    }

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


}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccDaNMRs.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status