Submission #487516

#	Time	Username	Problem	Language	Result	Execution time	Memory
487516		thiago_bastos	Race (IOI11_race)	C++17	100 / 100	451 ms	109644 KiB

race

#include "race.h"
#include <vector>
#include <set>
#include <utility>
#include <functional>

using namespace std;

using ii = pair<int, int>;
using i64 = long long;

int best_path(int N, int K, int H[][2], int L[])
{	
  vector<vector<ii>> g(N);
  vector<i64> pre(N);
  vector<set<pair<i64, int>>> S(N);
  int ans = N + 1;
  
  for(int i = 0; i < N - 1; ++i) {
  	int u = H[i][0], v = H[i][1];
  	g[u].emplace_back(v, L[i]);
  	g[v].emplace_back(u, L[i]);
  }
  
  pre[0] = 0;
  
  function<void(int, int, int)> dfs = [&](int u, int p, int h) {
  	
  	S[u].insert(make_pair(pre[u], h));
  	
  	for(auto [v, w] : g[u]) {
  		if(v == p) continue;
  		
  		pre[v] = pre[u] + w;
  		dfs(v, u, h + 1);
  		
  		if(S[v].size() > S[u].size()) swap(S[u], S[v]);
  		
  		for(auto [cost, depth] : S[v]) {
  			i64 X = K - cost + 2 * pre[u];
  			auto k = S[u].lower_bound(make_pair(X, -1));
  			if(k == S[u].end() || k->first != X) continue;
  			ans = min(ans, depth + k->second - 2 * h);
  		}
  		
  		for(auto [cost, depth] : S[v]) S[u].insert(make_pair(cost, depth));
  	}
  };
  
  dfs(0, 0, 0);
  
  if(ans == N + 1) ans = -1;
  
  return ans;
}

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