Submission #857828

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

race

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using namespace std;
#define ALL(x) x.begin(), x.end()
#define N 200005
#define K 1000005

int n, k, sz[N], dead[N], z = 1e9, dp[K];
vector<pair<int, int>> g[N];
vector<int> accessed;

int dfs(int u, int p)
{
    sz[u] = 1;
    for (auto [w, v] : g[u]) if (v != p && !dead[v]) sz[u] += dfs(v, u);
    return sz[u];
}

int get_centroid(int u, int p, int tn)
{
    for (auto [w, v] : g[u]) if (v != p && !dead[v] && sz[v] * 2 >= tn) return get_centroid(v, u, tn);
    return u;
}

void count(int u, int p, int fil, int dis, int dep)
{
    if (dis > k) return;
    accessed.push_back(dis);
    if (fil) dp[dis] = min(dp[dis], dep);
    else z = min(z, dp[k-dis] + dep);
    for (auto [w, v] : g[u])
        if (v != p && !dead[v]) count(v, u, fil, dis+w, dep+1);
}

void decomp(int u)
{
    u = get_centroid(u, -1, dfs(u, -1));
    dead[u] = 1;

    dp[0] = 0;

    for (auto [w, v] : g[u]) if (!dead[v]) count(v, u, 0, w, 1), count(v, u, 1, w, 1);

    for (auto x : accessed) dp[x] = 1e9+40;
    accessed.clear();

    for (auto [w, v] : g[u]) if (!dead[v]) decomp(v);

}

int best_path(int n0, int k0, vector<vector<int>> h, vector<int> l)
{
    memset(dp, 63, sizeof dp);
    
    for (int i = 0; i < h.size(); ++i)
    {
        int u = h[i][0], v = h[i][1], w=l[i];
        g[u].emplace_back(w, v), g[v].emplace_back(w, u);
    }

    decomp(0);

    return (z < 1e9) ? z : -1;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, std::vector<std::vector<int> >, std::vector<int>)':
race.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int i = 0; i < h.size(); ++i)
      |                     ~~^~~~~~~~~~
/usr/bin/ld: /tmp/cc8XYZac.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