Submission #1192440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192440		farica	Race (IOI11_race)	C++20	9 / 100	121 ms	32632 KiB

race

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

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

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

void dfs(int pos, int prev, int sum) {
	paths[pos][sum] = depth[pos];
	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].begin(); it != paths[adj.first].end(); ++it) {
			if(!paths[pos][it->first]) paths[pos][it->first] = it->second;
			else paths[pos][it->first] = min(paths[pos][it->first], it->second);
		}
	}
	if(paths[pos][sum+k]) {
		int cur = paths[pos][sum+k] - depth[pos];
		if(ans == -1) ans = cur;
		else ans = min(ans, cur);
	}
}

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]});
  }
  dfs(0,0,0);
  if(paths[0][k]) {
		int cur = paths[0][k];
		if(ans == -1) ans = cur;
		else ans = min(ans, cur);
	}
  
  return ans;
}

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