Submission #1192481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192481		farica	Race (IOI11_race)	C++20	100 / 100	321 ms	102604 KiB

race

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

using namespace std;
using vi = vector<int>;
using pi = pair<long long,long long>;
typedef long long ll;

ll ans, k;
vector<ll> depth;
vector<map<ll,int>>paths;
vector<vector<pi>>adjL;

void dfs(int pos, int prev, ll sum) {
	paths[pos][sum] = depth[pos];
	ll target = k + 2*sum;
	for(pi adj: adjL[pos]) {
		if(adj.first == prev) continue;
		depth[adj.first] = depth[pos] + 1;
		dfs(adj.first, pos, sum + adj.second);
		if(paths[adj.first].size() > paths[pos].size()) swap(paths[adj.first], paths[pos]);
		for(auto it: paths[adj.first]) {
			if(paths[pos].find(target - it.first) != paths[pos].end()) {
				ll cur = paths[pos][target-(it.first)] + (it.second) - 2 * depth[pos];
				if(ans == -1) ans = cur;
				else ans = min(ans, cur);
			}
		}
		for(auto it: paths[adj.first]) {
			if(paths[pos].find(it.first) == paths[pos].end()) paths[pos].insert(it);
			else paths[pos][it.first] = min(paths[pos][it.first], it.second);
		}
	}
}

int best_path(int N, int K, int H[][2], int L[]) {	
  ans = -1; 
  k = K;
  paths.resize(N);
  depth.assign(N, 0);
  adjL.assign(N, vector<pi>());
  for(int i=0; i<N-1; ++i) {
	adjL[H[i][0]].push_back({H[i][1], L[i]});
	adjL[H[i][1]].push_back({H[i][0], L[i]});
  }
  depth[0] = 1;
  dfs(0,0,0);
  
  return ans;
}

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