Submission #778471

#	Time	Username	Problem	Language	Result	Execution time	Memory
778471		Zflop	Race (IOI11_race)	C++14	0 / 100	7 ms	14420 KiB

race

#include <bits/stdc++.h>

using namespace std;

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

#define pb push_back

#define f first
#define s second
#define pi pair<int,int>
vector<pi>ad[200000];
map<int,int>m[200000];
int ans = (int)1e9,x;
void dfs(int node,int parent,int depth,int cost){
	long long t = cost * 2 + x;
	m[node][cost] = depth;
	for (auto i : ad[node])
		if(i.first != parent){
			dfs(i.first,node,depth + 1,cost + i.second);
			if((int)m[i.first].size() > (int)m[node].size()) m[node].swap(m[i.first]);
			for (auto v : m[i.first])
				if(m[node].count(t - i.second))
					ans = min(ans,m[node][t - v.first] +  v.second - 2 * depth);
			for (auto v : m[i.first])
				if(m[node].count(v.first)) m[node][v.first] = min(m[node][v.first],v.second);
				else m[node][v.first] = v.second;
			}
	}

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(1,0,0,0);
	return ans == (int)1e9 ? -1 : ans;
}

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