Submission #1098543

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1098543	2024-10-09T13:56:34 Z	SulA	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KB

race

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define bitcount __builtin_popcountll
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<long long,null_type,less_equal<>,rb_tree_tag,tree_order_statistics_node_update>;

map<long long, int> stl[200'000];
vector<pair<int,int>> adj[200'000];
int dep[200'000], ans = 1e9;
long long dist[200'000], k;

void init(int u = 0, int p = 0) {
    stl[u][dist[u]] = dep[u];
    for (auto [v, w] : adj[u]) if (v != p) {
        dep[v] = dep[u] + 1;
        dist[v] = dist[u] + w;
        init(v, u);
    }
}

void dfs(int u = 0, int p = 0) {
    long long target = k + 2*dist[u];
    for (auto [v, w] : adj[u]) if (v != p) {
        dfs(v, u);

        if (stl[v].size() > stl[u].size()) swap(stl[u], stl[v]);
        for (auto [len, edges] : stl[v]) {
            if (stl[u].count(target - len)) {
                cout << u << " " << v << "\n";
                cout << len << " " << target - len << '\n';
                ans = min(ans, stl[u][target - len] + edges - 2*dep[u]);
            }
        }
        for (auto [len, edges] : stl[v]) {
            if (stl[u].count(len)) {
                stl[u][len] = min(stl[u][len], edges);
            } else {
                stl[u][len] = edges;
            }
        }
    }
//    cout << u << ":\n";
//    for (auto [len, edges] : stl[u]) cout << len << " " << edges << "\n";
//    cout << '\n';
}

int best_path(int n, int _k, vector<vector<int>> h, vector<int> l) {
    k = _k;
    for (int i = 0; i < n-1; i++) {
        adj[h[i][0]].emplace_back(h[i][1], l[i]);
        adj[h[i][1]].emplace_back(h[i][0], l[i]);
    }
    init();
    dfs();
    return ans == 1e9 ? -1 : ans;
}

Compilation message

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