Submission #1166942

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

race

#include <iostream>

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 (maksPoddrzewo <= calaWielkosc / 2) return v;

    return -1;
}

vector<pair<ll, int>> odleglosci;

void policzOdleglosci(int v, int 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);
    }
}


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);
            }
        }
    }


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

    return wynik;

}



int best_path(int N, int K, vector<vector<int>>& H, vector<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;


}

Compilation message (stderr)

race.cpp:9:1: error: 'vector' does not name a type
    9 | vector<pair<int, int>> graf[MAXN];
      | ^~~~~~
race.cpp: In function 'void PoliczWielkoscPoddrzew(int, int)':
race.cpp:18:25: error: 'graf' was not declared in this scope
   18 |     for (auto& [s, w] : graf[v]){
      |                         ^~~~
race.cpp: In function 'int znajdzCentorid(int, int, int)':
race.cpp:29:25: error: 'graf' was not declared in this scope
   29 |     for (auto& [s, w] : graf[v]){
      |                         ^~~~
race.cpp: At global scope:
race.cpp:42:1: error: 'vector' does not name a type
   42 | vector<pair<ll, int>> odleglosci;
      | ^~~~~~
race.cpp: In function 'void policzOdleglosci(int, int, ll, ll)':
race.cpp:45:5: error: 'odleglosci' was not declared in this scope
   45 |     odleglosci.push_back({aktOdl, g});
      |     ^~~~~~~~~~
race.cpp:46:25: error: 'graf' was not declared in this scope
   46 |     for (auto& [s, w] : graf[v]){
      |                         ^~~~
race.cpp: In function 'int centroidDecomp(int)':
race.cpp:61:5: error: 'unordered_map' was not declared in this scope
   61 |     unordered_map<ll, int> bestOdl;
      |     ^~~~~~~~~~~~~
race.cpp:2:1: note: 'std::unordered_map' is defined in header '<unordered_map>'; did you forget to '#include <unordered_map>'?
    1 | #include <iostream>
  +++ |+#include <unordered_map>
    2 | 
race.cpp:61:21: error: expected primary-expression before ',' token
   61 |     unordered_map<ll, int> bestOdl;
      |                     ^
race.cpp:61:23: error: expected primary-expression before 'int'
   61 |     unordered_map<ll, int> bestOdl;
      |                       ^~~
race.cpp:62:5: error: 'bestOdl' was not declared in this scope
   62 |     bestOdl[0] = 0;
      |     ^~~~~~~
race.cpp:64:25: error: 'graf' was not declared in this scope
   64 |     for (auto& [s, w] : graf[centr]){
      |                         ^~~~
race.cpp:66:13: error: 'odleglosci' was not declared in this scope
   66 |             odleglosci.clear();
      |             ^~~~~~~~~~
race.cpp:81:25: error: 'graf' was not declared in this scope
   81 |     for (auto& [s, w] : graf[centr]){
      |                         ^~~~
race.cpp: At global scope:
race.cpp:93:36: error: 'vector' was not declared in this scope
   93 | int best_path(int N, int K, vector<vector<int>>& H, vector<int>& L){
      |                                    ^~~~~~
race.cpp:2:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
    1 | #include <iostream>
  +++ |+#include <vector>
    2 | 
race.cpp:93:36: error: 'vector' was not declared in this scope
   93 | int best_path(int N, int K, vector<vector<int>>& H, vector<int>& L){
      |                                    ^~~~~~
race.cpp:93:36: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
race.cpp:93:36: error: 'vector' was not declared in this scope
race.cpp:93:36: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
race.cpp:93:36: error: 'vector' was not declared in this scope
race.cpp:93:36: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
race.cpp:93:29: error: 'vector' has not been declared
   93 | int best_path(int N, int K, vector<vector<int>>& H, vector<int>& L){
      |                             ^~~~~~
race.cpp:93:35: error: expected ',' or '...' before '<' token
   93 | int best_path(int N, int K, vector<vector<int>>& H, vector<int>& L){
      |                                   ^
race.cpp: In function 'int best_path(int, int, int)':
race.cpp:97:9: error: 'graf' was not declared in this scope
   97 |         graf[H[i][0]].push_back({H[i][1], L[i]});
      |         ^~~~
race.cpp:97:14: error: 'H' was not declared in this scope
   97 |         graf[H[i][0]].push_back({H[i][1], L[i]});
      |              ^
race.cpp:97:43: error: 'L' was not declared in this scope
   97 |         graf[H[i][0]].push_back({H[i][1], L[i]});
      |                                           ^