Submission #212443

#	Time	Username	Problem	Language	Result	Execution time	Memory
212443		_qVp_	Race (IOI11_race)	C++14	9 / 100	3106 ms	137716 KiB

race

#include <iostream> 
#include <map>
#include <vector>
using namespace std;

const int MAXN = 2e5 + 10;
const long long oo = 1e18;

typedef pair < int, int > II;

long long sz[MAXN], depth[MAXN], sum[MAXN];
vector < II > adj[MAXN];
vector < int > vec[MAXN];
map < long long, long long > path;
int h[MAXN][2], l[MAXN];
int n, k;
long long ans = oo;

void dfs(int u, int p) {
	sz[u] = 1;
	for(int i = 0; i < adj[u].size(); i++) {
		II cur = adj[u][i];
		int v = cur.first, w = cur.second;
		if (v == p)
			continue;
		depth[v] = depth[u] + 1;
		sum[v] = sum[u] + w;
		dfs(v, u);
		sz[u] += sz[v];
	}
}

void add(int u, int k) {
	long long sumNow = sum[u];
	long long & temp = path[sumNow]; 
	if (k == -1) {
		path[sumNow] = 0;
	} else {
		long long tmp = temp;
		if (tmp == 0)
			tmp = oo;
		temp = min(tmp, depth[u]);
	}
}

void sack(int u, int p, int keep) {
	int szMax = -1, bigChild = -1;
	
	for(int i = 0; i < adj[u].size(); i++) {
		int v = adj[u][i].first;
		if (v == p)
			continue;
		if (sz[v] > szMax) {
			sz[v] = szMax;
			bigChild = v;
		}
	}
	
	for(int i = 0; i < adj[u].size(); i++) {
		int v = adj[u][i].first;
		if (v != bigChild && v != p)
			sack(v, u, 0);
	}
	
	if (bigChild != -1) {
		sack(bigChild, u, 1);
		swap(vec[u], vec[bigChild]);
	}
	
	vec[u].push_back(u);
	add(u, 1);
	if (path[k + sum[u]])
		ans = min(ans, path[k + sum[u]] - depth[u]);
	for(int i = 0; i < adj[u].size(); i++) {
		int v = adj[u][i].first;
		if (v == p || v == bigChild)
			continue;
		for(int j = 0; j < vec[v].size(); j++) {
			int x = vec[v][j];
			long long need = k + sum[u] * 2 - sum[x];
			if (path[need]) 
				ans = min(ans, path[need] + depth[x] - 2 * depth[u]);
			add(x, 1);
			vec[u].push_back(x);
		}
	}
	
	if (!keep) {
		for(int i = 0; i < vec[u].size(); i++) {
			int v = vec[u][i];
			add(v, -1);
		}
	}
	
}

int solve() {
	dfs(0, -1);
	sack(0, -1, 1);
	return (ans == oo ? -1 : ans);
}

int best_path(int N, int K, int H[][2], int L[]) {
	n = N, k = K;
	for(int i = 0; i < n - 1; i++) {
		int u = H[i][0], v = H[i][1], w = L[i];
		adj[u].push_back(II(v, w));
		adj[v].push_back(II(u, w));
	}
	return solve();
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:21:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~
race.cpp: In function 'void sack(int, int, int)':
race.cpp:49:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~
race.cpp:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~
race.cpp:74:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < adj[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~
race.cpp:78:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < vec[v].size(); j++) {
                  ~~^~~~~~~~~~~~~~~
race.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < vec[u].size(); i++) {
                  ~~^~~~~~~~~~~~~~~

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