Submission #711883

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

race

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

#define N 200000
#define MAX 1000000000
#define E 0.00000001
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFll 0x3f3f3f3f3f3f3f3fll
#define LEFT(x) (2 * x)
#define RIGHT(x) (2 * x + 1)
#define se second
#define fi first

using namespace std;

typedef long long ll;

vector<int> g[N+1];
map<pair<int,int>, ll> e;
map<ll,int> d[N+1];
ll dist[N+1];
int sz[N+1];
int ans = -1;

void prec(int u, int p){
	dist[u] = dist[p] + e[{u,p}];
	for(int v : g[u]){
		if(v == p) continue;
		prec(v, u);
	}
}

void solve(int u, int p, int depth, ll k){
	
	int big = -1;
	sz[u] = 1;
	
	for(int v : g[u]){
		if(v == p) continue;
		solve(v, u, depth+1, k);
		sz[u] += sz[v];
		if(big == -1 or sz[v] > sz[big]) big = v;
	}

	if(big == -1){
		d[u][dist[u]] = depth;	
		return;
	}

	swap(d[u], d[big]);

	d[u][dist[u]] = depth;

	if(d[u].count(k + dist[u])){
		if(ans == -1) ans = d[u][k + dist[u]] - depth;
		else  ans = min(ans, d[u][k + dist[u]] - depth);
	}

	for(int v : g[u]){
		if(v == p or v == big) continue; 
		for(auto i : d[v]){
			if(d[u].count(i.fi)){
				d[u][i.fi] = min(d[u][i.fi], i.se);
			}
			else{
				d[u][i.fi] = i.se;
			}

			ll want = k + 2 * dist[u] - i.fi;
			if(d[u].count(want)){
				if(ans == -1) ans = (d[u][i.fi] - depth) + (d[u][want] - depth); 
				else ans = min(ans, (d[u][i.fi] - depth) + (d[u][want] - depth));
			}
		}
	}
}

int best_path(int n, int k, int* h[2], int* l){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	for(int i = 1; i <= n; i++){
		g[i].clear();
		dist[i] = 0;
		sz[i] = 0;
		d[i].clear();
	}
	ans = -1;
	e.clear();

	for(int i = 0; i < n; i++){
		ll u, v, w;
		u = h[i][0];
		v = h[i][1];
		w = l[i];

		u++;
		v++;

		g[u].push_back(v);
		g[v].push_back(u);
		e[{u,v}] = w;
		e[{v,u}] = w;
	}

	prec(1,0);
	solve(1, 0, 0, k);

	cout << ans << endl;

    return 0;
}

Compilation message (stderr)

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