Submission #1272048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272048		ciceroknopfler	경주 (Race) (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>
using namespace std;
using uint = unsigned;

vector<vector<pair<int, uint>>> adjList; // (vertex, weight)
vector<int> subtrees;
vector<bool> blocked;
vector<pair<uint,uint>> paths;
uint K, N, answer;

template <class T> class flagArray {
public:
    flagArray(uint size = 0) : _size(size) {
        _array = new pair<T, uint>[size];
    };
    ~flagArray() { delete[] _array; };

    uint getFlag() const { return _flag; };
    void newFlag() { ++_flag; };

    pair<T, uint> &operator[](uint idx) { return _array[idx]; };

private:
    pair<T, uint> *_array;
    uint _flag{0}, _size{0};
};

flagArray<uint> farray(1000001);

inline int dfsFindCentroid(int u, int p) {
    subtrees[u] = 1;
    for (auto [v, w] : adjList[u])
        if (v != p && !blocked[v])
            subtrees[u] += dfsFindCentroid(v, u);
    return subtrees[u];
}

inline int findCentroid(int u, int p, int n) {
    for (auto [v, w] : adjList[u])
        if (v != p && !blocked[v] && subtrees[v] > n / 2)
            return findCentroid(v, u, n);
    return u;
}

inline void dfsPaths(int u, int p, uint dist, uint depth) {
    if (dist > K)
      return;
    paths.push_back({dist, depth});
    for (auto [v, w] : adjList[u])
        if (v != p && !blocked[v])
            dfsPaths(v, u, dist + w, depth + 1);
}

void decompose(int u) {
    int centroid = findCentroid(u, -1, dfsFindCentroid(u, -1));
    blocked[centroid] = true;
    farray.newFlag();

    farray[0] = {0, farray.getFlag()};
    for (auto [v, w] : adjList[centroid]) {
        if (blocked[v])
          continue;
        paths.clear();
        dfsPaths(v, centroid, w, 1);

        for (auto [dist, depth] : paths)
            if (K >= dist) {
                auto p = farray[K - dist];
                if (p.second == farray.getFlag())
                    answer = min(answer, (p.first + depth));
            }

        for (auto [dist, depth] : paths) {
            auto &p = farray[dist];
            if (p.second != farray.getFlag() || depth < p.first)
                p = {depth, farray.getFlag()};
        }
    }

    for (auto [v, w] : adjList[centroid])
        if (!blocked[v]) decompose(v);
}

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

    adjList.assign(N, {});
    subtrees.assign(N, 0);
    blocked.assign(N, false);

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

    decompose(0);

    if(answer == UINT_MAX)
      return -1;
    return answer;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccHeLDif.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