QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#145338#2002. RaceK8HeCompile Error//C++203.0kb2023-08-22 08:30:492023-08-22 08:30:50

Judging History

你现在查看的是最新测评结果

  • [2023-08-22 08:30:50]
  • 评测
  • [2023-08-22 08:30:49]
  • 提交

answer

#include <bits/stdc++.h>
#define lowb(a, r, x) lower_bound(a + 1, a + r + 1, x) - a
#define uppb(a, r, x) upper_bound(a + 1, a + r + 1, x) - a
#define _for(i, a, b) for (ll i = a; i <= b; ++i)
#define for_(i, a, b) for (ll i = a; i >= b; --i)
#define far(i, vec) for (auto i : vec)
#define bdmd ll mid = (l + r) >> 1
#define NO nullptr
typedef long double ldb;
typedef long long ll;
typedef double db;
typedef std::pair <ll, ll> pll;
const ll N = 2e5 + 10, K = 1e6 + 10, inf = 1ll << 60;
namespace SOLVE {
	ll n, k, root, sz[N], mx[N], len[K], ans;
	std::vector <pll> tu[N], tmp;
	bool vis[N];
	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
	void GetDis (ll u, ll fa, ll s, ll d) {
		if (s > k) return;
		// printf ("%lld %lld %lld  %lld %lld  %lld %lld\n", u, fa, d, s, t, len[s], len[t]);
		tmp.emplace_back (s, d);
		far (p, tu[u]) {
			ll v = p.first, w = p.second;
			if (vis[v] || v == fa) continue;
			GetDis (v, u, s + w, d + 1);
		}
		return;
	}
	void Clear (ll u, ll fa, ll s, ll d) {
		if (s > k) return;
		len[s] = inf;
		far (p, tu[u]) {
			ll v = p.first, w = p.second;
			if (vis[v] || v == fa) continue;
			Clear (v, u, s + w, d + 1);
		}
		return;
	}
	inline void Calc (ll u) {
		// printf ("%lld %lld\n", u, ans);
		far (p, tu[u]) {
			ll v = p.first, w = p.second;
			if (vis[v]) continue;
			GetDis (v, u, w, 1);
			far (j, tmp) {
				ll t = k - j.first;
				if (len[t] < inf) ans = std::min (ans, len[t] + j.second);//, printf ("%lld %lld  %lld %lld  %lld\n", t, len[t], j.first, j.second, ans);
			}
			far (j, tmp) len[j.first] = std::min (len[j.first], j.second);
			std::vector <pll> ().swap (tmp);
			// printf ("%lld %lld\n", v, ans);
		}
		Clear (u, 0, 0, 0);
		// printf ("%lld %lld\n", u, ans);
		// puts ("");
		return;
	}
	void GetRoot (ll u, ll fa) {
		sz[u] = 1, mx[u] = 0;
		far (p, tu[u]) {
			ll v = p.first, w = p.second;
			if (vis[v] || v == fa) continue;
			GetRoot (v, u), sz[u] += sz[v];
			mx[u] = std::max (mx[u], sz[v]);
		}
		mx[u] = std::max (mx[u], sz[0] - sz[u]);
		if (mx[u] < mx[root]) root = u;
		return;
	}
	void Divide (ll u) {
		Calc (u);
		vis[u] = true;
		far (p, tu[u]) {
			ll v = p.first, w = p.second;
			if (vis[v]) continue;
			sz[0] = sz[v], mx[root = 0] = inf;
			GetRoot (v, u);
			Divide (root);
		}
		return;
	}
	inline void In () {
		n = rnt (), k = rnt ();
		_for (i, 1, n - 1) {
			ll u = rnt () + 1, v = rnt () + 1, w = rnt ();
			tu[u].emplace_back (v, w);
			tu[v].emplace_back (u, w);
		}
		return;
	}
	inline void Solve () {
		ans = inf, sz[0] = n, mx[root = 0] = inf;
		_for (i, 1, k) len[i] = inf;
		GetRoot (1, 0);
		Divide (root);
		return;
	}
	inline void Out () {
		printf ("%lld\n", ans == inf ? -1 : ans);
		return;
	}
}
int main () {
	SOLVE::In ();
	SOLVE::Solve ();
	SOLVE::Out ();
	return 0;
} /*

*/

Details

/usr/bin/ld: /tmp/ccOcDGGi.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccyMn3ph.o:implementer.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccyMn3ph.o: in function `main':
implementer.cpp:(.text.startup+0x26): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status