Submission #971548

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

race

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int msz = 2e5 + 5;
const int lg = 25;

struct edge{
    int to, t;
    edge(int a, int b){
        to = a; t = b;
    }
};

vector<edge> g[msz];
vector<int> cl[lg], out, sz;

void fill(int v, int pr){
    sz[v] = 1;
    for (auto i: g[v]){
        if (i.to == pr || out[i.to]) continue;
        fill(i.to, v);
        sz[v] += sz[i.to];
    }
}

int find(int v, int pr, int& x){
    for (auto i: g[v]){
        if (i.to == pr || out[i.to]) continue;
        if (2 * sz[i.to] >= x) return find(i.to, v, x);
    }
    return v;
}

void build(int v, int cnt){
    fill(v, 0);
    int u = find(v, 0, sz[v]);
    out[u] = cnt++;
    cl[out[u]].push_back(u);
    for (auto i: g[u]){
        if (out[i.to]) continue;
        build(i.to, cnt);
    }
}

vector<ll> weight;
vector<pair<int, int>> p;
vector<bool> used;

void fill_dfs(int v, int pr){
    for (auto i: g[v]){
        if (i.to == pr || used[i.to]) continue;
        weight[i.to] = weight[v] + i.t;
        fill_dfs(i.to, v);
    }
}

void add(int v, int pr, int cnt){
    p.push_back({v, cnt++});
    for (auto i: g[v]){
        if (i.to == pr || used[i.to]) continue;
        add(i.to, v, cnt);
    }
}

int ans = msz, l;

void solve(int v, int cnt){
    weight[v] = 0;
    used[v] = true;
    fill_dfs(v, 0);
    map<ll, int> mp;
    for (auto i: g[v]){
        if (used[i.to]) continue;
        add(i.to, 0, 1);
        for (auto j: p){
            if (weight[j.first] > l) continue;
            if (weight[j.first] == l){
                ans = min(ans, j.second);
                continue;
            }
            int x = mp[l - weight[j.first]];
            if (x > 0) ans = min(ans, j.second + x);
        }
        for (auto j: p){
            int val = mp[weight[j.first]];
            if (!val){
                mp[weight[j.first]] = j.second;
                continue;
            }
            mp[weight[j.first]] = min(val, j.second);
        }
        p.clear();
    }
}

int n;

void best_path(int ns, int ks, vector<pii> hs, vector<int> ls){
    n = ns; l = ks;
    for (int i = 0; i < hs.size(); i++){
        auto [u, v] = hs[i];
        u++; v++;
        g[u].push_back({v, ls[i]});
        g[v].push_back({u, ls[i]});
    }
    out.assign(n + 1, 0);
    sz.resize(n + 1);
    build(1, 1);
    weight.resize(n + 1);
    used.assign(n + 1, false);
    for (int i = 1; i < lg; i++){
        for (int j: cl[i]){
            solve(j, 1);
        }
    }
    if (ans == msz){
        cout<<-1;
        return;
    }
    cout<<ans;
}
// Old code

Compilation message (stderr)

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