Submission #1293629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293629		stathiskons	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

// 

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

using ll = long long;
using pi = pair<int, int>;

int k;
vector<vector<pi>> adj;
vector<int> sz;
vector<bool> erased;
// vector<map<int, int>> children;
map<int, int> children;

int ans = INT_MAX;

void get_sz(int i, int p) {
    sz[i] = 1;
    for(auto [u, c] : adj[i]) {
        if(u == p || erased[u]) continue;

        get_sz(u, i);
        sz[i] += sz[u];
    }
}

int centroid(int i, int p, int n) {
    for(auto [u, c] : adj[i]) {
        if(u == p || erased[u]) continue;

        if(sz[u] > n/2) return centroid(u, i, n);
    }
    return i;
}

void dfs(int i, int p, ll d, int steps, bool add) {
    if(d > k) return;
    if(add) {
        auto it = children.find(d);
        if(it == children.end()) children[d] = steps;
        else it->second = min(it->second, steps);
    } else {
        auto it = children.find(k - d);
        if(it != children.end()) ans = min(ans, steps + it->second);
    }

    for(auto [u, c] : adj[i]) {
        if(u == p || erased[u]) continue;

        dfs(u, i, d + c, steps + 1, add);
    }
}

void decompose(int i) {
    get_sz(i, i);
    i = centroid(i, i, sz[i]);

    children.clear();
    children[0] = 0;
    for(int add = 0 ; add < 2 ; add) {
        for(auto [u, c] : adj[i]) {
            if(erased[u]) continue;
            
            dfs(u, i, c, 1, false);
        }
    }
        
    erased[i] = true;

    for(auto [u, c] : adj[i]) {
        if(!erased[u]) decompose(u);
    }
}

int best_path(int n, int K, int edges[][2], int l[]) {
    k = K;
    adj.resize(n + 1);
    for(int i = 0 ; i < n - 1 ; i++) {
        int a = edges[i][0];
        int b = edges[i][1];
        int c = l[i];

        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
    }

    sz.resize(n + 1);
    erased.resize(n + 1);

    decompose(1);

    cout << ans << "\n";
}


int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t; cin >> t; while(t--) solve();
    
    return 0;
}

Compilation message (stderr)

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:94:1: warning: no return statement in function returning non-void [-Wreturn-type]
   94 | }
      | ^
race.cpp: In function 'int main()':
race.cpp:101:33: error: 'solve' was not declared in this scope
  101 |     int t; cin >> t; while(t--) solve();
      |                                 ^~~~~