Submission #711913

#	Time	Username	Problem	Language	Result	Execution time	Memory
711913		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<ll> g[N+1];
map<pair<ll,ll>, ll> e;
map<ll,ll> d[N+1];
ll dist[N+1];
ll sz[N+1];
ll ans = -1;

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

void solve(ll u, ll p, ll depth, ll k){
	
	ll big = -1;
	sz[u] = 1;
	
	for(ll 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(ll 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));
			}
		}
	}
}

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

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

	for(ll i = 0; i < n-1; 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);

	return ans;
}

Compilation message (stderr)

race.cpp:79:4: error: ambiguating new declaration of 'll best_path(int, int, int (*)[2], int*)'
   79 | ll best_path(int n, int k, int (*h)[2], int* l){
      |    ^~~~~~~~~
In file included from race.cpp:1:
race.h:1:5: note: old declaration 'int best_path(int, int, int (*)[2], int*)'
    1 | int best_path(int N, int K, int H[][2], int L[]);
      |     ^~~~~~~~~