Submission #836009

#	Time	Username	Problem	Language	Result	Execution time	Memory
836009		Halym2007	Race (IOI11_race)	C++11	100 / 100	375 ms	47152 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define N 200005
const int INF = 1e9 + 7;
vector <int> nodes;
int dpt[N], types[N], mx = 1e9, rem[N], sub[N];
ll baha[N];
vector <pair <int, int>> v[N], G[N];
int p[1000005];
void dfs (int x, int pr) {
	sub[x] = 1;
	for (auto i : v[x]) {
		if (i.ff == pr or rem[i.ff]) {
			continue;
		}
		dfs (i.ff, x);
		sub[x] += sub[i.ff];
	}
}
int centroid (int x, int pr, int san) {
	for (auto i : v[x]) {
		if (i.ff == pr or rem[i.ff]) continue;
		if (sub[i.ff] > san / 2) {
			return centroid (i.ff, x, san);
		}
	}
	return x;
}

void solve (int x, int pr,  ll val, int type, int edge) {
//	cout << x << " " << val << " " << type << " " << edge << endl;
	baha[x] = val;
	types[x] = type;
	dpt[x] = edge;
	nodes.pb (x);
	for (auto i : v[x]) {
		if (i.ff == pr or rem[i.ff]) continue;
		solve (i.ff, x, val + i.ss, type, edge + 1);
	}
}



void build (int x, int pr, int k) {
	int centr = centroid (x, -1, sub[x]); // centr tapdyk
	rem[centr] = 1;
	int at = 0;
	nodes.clear();
	for (auto i : v[centr]) {
		if (rem[i.ff]) continue;
		solve (i.ff, 0, i.ss, ++at, 1);
	}
	for (int i : nodes) {
		G[types[i]].pb ({baha[i], dpt[i]});
	}
	for (int i = 1; i <= at; ++i) {
		for (auto j : G[i]) {
			if (j.ff <= k) {
				mx = min (mx, p[k - j.ff] + j.ss);
			}
		}
		for (auto j : G[i]) {
			if (j.ff <= k) {
				p[j.ff] = min (p[j.ff], j.ss);
			}
		}
		G[i].clear();
	}
	for (int i : nodes) if (baha[i] <= k) p[baha[i]] = INF;
	for (auto i : v[centr]) {
		if (rem[i.ff]) {
		continue;
		}
		dfs (i.ff, -1);
		build (i.ff, centr, k);
	}
}


int best_path(int n, int k, int h[][2], int l[]) {
	for (int i = 1; i <= k; ++i) p[i] = INF;
	for (int i = 0; i < n - 1; ++i) {
		int u = h[i][0], vv = h[i][1], w = l[i];
		v[u].pb ({vv, w});
		v[vv].pb ({u, w});
	}
	dfs (0, -1);
	build (0, -1, k);
	if (mx == 1e9) mx = -1;
	return mx;
}


//#define MAX_N 500000
//int n, k;
//int h[MAX_N][2];
//int l[MAX_N];
//
//int main() {
//	freopen ("input.txt", "r", stdin);
//  cin >> n >> k;
//  for(int i = 0; i < n-1; i++)
//    cin >> h[i][0] >> h[i][1] >> l[i];
//  int ans;
//  ans = best_path(n,k,h,l);
//  cout << ans << "\n";
//  return 0;
//}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57