Submission #896707

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

race

#include "race.h"
#include <bits/stdc++.h>
#define int long long 
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << endl, exit(0);
#define mp make_pair
#define pii pair<int, int>
#define pb push_back


using namespace std;

const int MAXN = (int)1e6 + 7;
const int MOD = 998244353;
const int INF = (int)1e9 + 7;

int n, m, t, u, v, w, tmp, tmp2, tmp3, tmp4, ans, k;
int arr[MAXN], cost[MAXN], sz[MAXN];
pii love[MAXN];
bool hate[MAXN];
vector<pii> adj[MAXN];


void DFSsz(int v, int p=-1) {
	sz[v] = 1;

	for (auto cur:adj[v]) {
		int u = cur.F, w = cur.S;

		if (!hate[u] && u != p) {
			DFSsz(u, v);
			sz[v] += sz[u];
		}
	}
}


int centroid(int tot, int v, int p=-1) {
	for (auto cur:adj[v]) {
		int u = cur.F, w = cur.S;

		if (u != p && !hate[u] && 2*sz[u] > tot) return centroid(tot, u, v);
	}

	return v;
}


void check_mol(int v, int cent, int p, pii dis, bool x) {
	if (dis.S > k) return;

	for (auto cur:adj[v]) {
		int u = cur.F, w = cur.S;

		if (u != p && !hate[u]) check_mol(u, cent, v, mp(dis.F+1, dis.S+w), x);
	}

	if (!x) {
		if (love[k-dis.S].F == cent) {
			ans = min(ans, dis.F+love[k-dis.S].S);
		}
	} else {
		if (love[dis.S].F != cent) {
			love[dis.S].F = cent;
			love[dis.S].S = dis.F;
		} else {
			love[dis.S].S = min(love[dis.S].S, dis.F);
		}
	}
}


void solve(int v) {
	DFSsz(v);
	int cent = centroid(sz[v], v);


	for (auto cur:adj[v]) {
		int u = cur.F, w = cur.S;
		if (hate[u]) continue;

		check_mol(u, cent, cent, mp(1, w), 0);
		check_mol(u, cent, cent, mp(1, w), 1);
	}

	hate[cent] = 1;
	for (auto cur:adj[v]) if (!hate[cur.F]) solve(cur.F);
}


int best_path(int N, int K, int H[][2], int L[]) {
	n = N, k=K;

	for (int i=0; i<n; i++) {
		u = H[i][0];
		v = H[i][1];
		w = L[i];
		u++, v++;

		adj[u].pb(mp(v, w));
		adj[v].pb(mp(u, w));
	}

	ans = INF;

	solve(1);

	if (ans == INF) return -1;
	return ans;
}

Compilation message (stderr)

race.cpp: In function 'void DFSsz(long long int, long long int)':
race.cpp:30:18: warning: unused variable 'w' [-Wunused-variable]
   30 |   int u = cur.F, w = cur.S;
      |                  ^
race.cpp: In function 'long long int centroid(long long int, long long int, long long int)':
race.cpp:42:18: warning: unused variable 'w' [-Wunused-variable]
   42 |   int u = cur.F, w = cur.S;
      |                  ^
/usr/bin/ld: /tmp/cck47oPv.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