Submission #833715

#	Time	Username	Problem	Language	Result	Execution time	Memory
833715		kingfran1907	Race (IOI11_race)	C++14	9 / 100	104 ms	37664 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 2e5+10;
const int maxk = 1e6+10;
const int inf = 0x3f3f3f3f;

int n, k;
vector< pair<int, int> > graph[maxn];
map< llint, llint > s[maxn];
llint sol = inf;
llint ofx[maxn], ofy[maxn];

void solve(int x, int parr) {
	//printf("solving: %d %d\n", x, parr);
	s[x][0] = 0;
	for (auto iter : graph[x]) {
		int tren = iter.X;
		int cost = iter.Y;
		if (tren == parr) continue;
		solve(tren, x);
		
		//printf("merging %d %d\n", x, tren);
		if (s[tren].size() > s[x].size()) {
			//printf("child is larger\n");
			swap(s[tren], s[x]);
			swap(ofx[tren], ofx[x]);
			swap(ofy[tren], ofy[x]);
			ofy[x]++;
			ofx[x] += cost;
			
			for (auto iter : s[tren]) {
				llint dis = iter.X + ofx[tren];
				//printf("trying: %lld\n", dis);
				if (s[x].count(k - dis - ofx[x])) 
					sol = min(sol, s[x][k - dis - ofx[x]] + iter.Y + ofy[tren] + ofy[x]);
				
				dis -= ofx[x];
				if (s[x].count(dis)) s[x][dis] = min(s[x][dis], iter.Y + ofy[tren] - ofy[x]);
				else s[x][dis] = min(s[x][dis], iter.Y + ofy[tren] - ofy[x]);
			}
		} else {
			//printf("parrent is larger\n");
			for (auto iter : s[tren]) {
				llint dis = iter.X + ofx[tren] + cost;
				//printf("trying %lld\n", dis);
				if (s[x].count(k - dis - ofx[x])) 
					sol = min(sol, s[x][k - dis - ofx[x]] + iter.Y + 1 + ofy[tren] + ofy[x]);
				
				dis -= ofx[x];
				if (s[x].count(dis)) s[x][dis] = min(s[x][dis], iter.Y + 1);
				else s[x][dis] = iter.Y + 1;
			}
		}
	}
}

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 a = H[i][0];
		int b = H[i][1];
		graph[a].push_back({b, L[i]});
		graph[b].push_back({a, L[i]});
	}
	solve(0, -1);
	if (sol == inf) return -1;
	return sol;
}

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