Submission #1244263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244263		enjeeeff	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

#include<iostream>
#include<vector>
#include<map>
#include<set>
typedef long long ll;
#define vec vector
using namespace std;

struct Centroid {
    vec<vec<pair<ll, ll> > > adj;
    vec<ll> s, deleted;
    ll ans = 1e18, k;
    map<ll, multiset<ll> > mp, mp1;

    Centroid(ll n, ll dist) {
        k = dist;
        s.assign(n + 1, 0);
        deleted.assign(n + 1, 0);
        adj.assign(n + 1, {});
        // mp.assign(n + 1, {});
        // mp1.assign(n + 1, {});
    }

    void add(ll a, ll b, ll w) {
        adj[a].emplace_back(b, w);
        adj[b].emplace_back(a, w);
    }

    void count_sizes(ll v, ll par = -1) {
        s[v] = 1;
        for (auto &e : adj[v])
            if (!deleted[v] && par != e.first) {
                count_sizes(e.first, v);
                s[v] += s[e.first];
            }
    }

    ll find_centroid(ll v, ll n, ll par = -1) {
        for (auto &e : adj[v])
            if (!deleted[v] && par != e.first && s[e.first] * 2 > n)
                return find_centroid(e.first, n, v);
        return v;
    }

    void fullfill(ll v, ll par, ll dist, ll dist1 = 1) {
        for (auto &e : adj[v])
            if (!deleted[e.first] && e.first != par)
                fullfill(e.first, v, dist + e.second, dist1 + 1);
        mp[dist].insert(dist1);
    }

    void fullfill1(ll v, ll par, ll dist, ll dist1 = 1) {
        if (dist == k)
            ans = min(dist1, ans);
        for (auto &e : adj[v])
            if (!deleted[e.first] && e.first != par)
                fullfill1(e.first, v, dist + e.second, dist1 + 1);
        mp1[dist].insert(dist1);
        auto &gotSet = mp[dist];
        gotSet.erase(gotSet.find(dist1));
    }

    void constructAnswer(ll v = 0) {
        count_sizes(v);
        ll cnt = find_centroid(v, s[v]);

        mp.clear();
        deleted[cnt] = 1;
        for (auto &e : adj[cnt]) {
            if (deleted[e.first]) continue;
            fullfill(e.first, cnt, e.second);
        }

        for (auto &e : adj[cnt]) {
            if (deleted[e.first]) continue;
            fullfill1(e.first, cnt, e.second);

            for (auto &ofLength : mp1) {
                auto p = mp.find(k - ofLength.first);
                if (p == mp.end() || !p->second.size()) continue;
                ans = min(*p->second.begin() + *ofLength.second.begin(), ans);
            }

            fullfill(e.first, cnt, e.second);
            mp1.clear();
        }

        for (auto &e : adj[cnt])
            if (!deleted[e.first])
                constructAnswer(e.first);
    }
};

int main() {
    ll n, k;
    cin >> n >> k;
    Centroid structure(n, k);

    while (--n) {
        ll a, b, w;
        cin >> a >> b >> w;
        structure.add(a, b, w);
    }
    structure.constructAnswer();

    cout << structure.ans << '\n';
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccrqFLZd.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccLGckJw.o:race.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccrqFLZd.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