Submission #778488

#	Time	Username	Problem	Language	Result	Execution time	Memory
778488		Zflop	Race (IOI11_race)	C++14	100 / 100	369 ms	104500 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define pb push_back

#define f first
#define s second

vector<pii>ad[200000];
map<ll,ll>m[200000];
ll ans = (ll)1e16,x;
void dfs(int node,int parent,int depth,ll cost){
	long long t = cost * 2 + x;
	m[node][cost] = depth;
	for (auto i : ad[node])
		if(i.f != parent){
			dfs(i.f,node,depth + 1,cost + i.s);
			if((int)m[i.f].size() > (int)m[node].size()) m[node].swap(m[i.f]);
			for (auto v : m[i.f])
				if(m[node].find(t - v.f) != m[node].end())
					ans = min(ans,m[node][t - v.f] +  v.s - 2 * depth);
			for (auto v : m[i.f])
				if(m[node].find(v.f) != m[node].end()) m[node][v.f] = min(m[node][v.f],v.s);
				else m[node].insert(v);
			}
	}

int best_path(int N, int K, int H[][2], int L[]){
	x = K;
	for (int i = 0; i < N - 1;++i){
		ad[H[i][0]].push_back({H[i][1],L[i]});
		ad[H[i][1]].push_back({H[i][0],L[i]});
		}
	dfs(0,0,0,0);
	return ans == (ll)1e16 ? -1 : ans;
}

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