Submission #1321409

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

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

#define ll long long
const ll mmod = 998244353;
#define vl vector<long long>
#define vll vector<vector<long long>>
#define pl pair<long long, long long>
#define vb vector<bool>

vector<vector<pl>> graf;
vb center;
vl sizes;
ll minimum = 1e15;

ll getsize(ll v, ll u){
    ll s = 1;
    for (auto x : graf[v]){
        if (center[x.first] == false && x.first != u){
            s += getsize(x.first, v);
        }
    }
    sizes[v] = s;
    return s;
}

ll findcentroid(ll v, ll u, ll n){
    ll a = 1;
    for (auto x : graf[v]){
        if (center[x.first] == false && x.first != u){
            a = findcentroid(x.first, v, n);
            if (a!=-1){
                return a;
            }
        }
    }
    if (sizes[v] >= n/2){
        return v;
    }
    else{
        return -1;
    }
}

void dists(ll v, ll u, ll d, ll depth, vector<pl>& dist, ll k){
    for (auto x : graf[v]){
        if (center[x.first] == false && x.first != u){
            if (d + x.second <= k){
                dist.push_back({d + x.second, depth});
                dists(x.first, v, d + x.second, depth + 1, dist, k);
            }
        }
    }
}

void decompose(ll v, ll k){
    ll comp = getsize(v,-1);
    ll c = findcentroid(v, -1, comp);
    center[c] = true;

    vector<pl> dist = {{0,0}}; // OPRAVENO: Syntaktická chyba, vektor párů nelze inicializovat jako {0,0}, musí být {{0,0}}
    for (auto x : graf[c]){
        vector<pl> newdist;
        if (center[x.first] == false){
            dists(c, -1, 0, 0, newdist, k);
        }
        sort(newdist.begin(), newdist.end());
        ll l = 0;
        ll r = newdist.size()-1;
        while (l < (ll)dist.size() && r >= 0){ // OPRAVENO: Přetypování na ll, aby se neporovnával signed (l) a unsigned (size)
            ll suma = dist[l].first + newdist[r].first;
            if (suma == k){
                minimum = min(minimum, dist[l].second + dist[r].second);
                r--;
            }
            if (suma < k){ // OPRAVENO: Chybělo 'else', pokud suma == k, provedlo se r-- a pak hned podmínka suma < k (původně bez else if by to mohlo zlobit, ale syntakticky ok). Přidal jsem else pro jistotu, ale pro kompilaci stačí původní. Nechávám původní flow.
                l++;
            }
            else{
                r--;
            }
        }
        if (dist.size() < newdist.size()){
            swap(dist, newdist);
        }
        for (ll i = 0; i < newdist.size(); i++){
            dist.push_back(newdist[i]);
        }
        sort(dist.begin(), dist.end());
        
    }
}

ll best_path(ll N, ll K, vll H, vl L){
    ll n = N; ll k = K;

    graf.resize(n);
    center.resize(n, false);
    sizes.resize(n,0);
    for (ll i = 0; i < n-1; i++){
        ll a,b;
        a = H[i][0]; b = H[i][1];
        ll c = L[i];
        graf[a].push_back({b,c});
        graf[b].push_back({a,c});

    }
    decompose(0, k);
    return minimum;
}

Compilation message (stderr)

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