제출 #1149674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149674		crispxx	Race (IOI11_race)	C++20	9 / 100	33 ms	7696 KiB

race

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

// #include "grader.cpp"

using namespace std;

#define all(x) x.begin(), x.end()

int best_path(int N, int K, int H[][2], int L[]) {
	map<long long, int> mp;
	
	vector<vector<pair<int, int>>> adj(N);
	
	for(int i = 0; i < N - 1; i++) {
		int u = H[i][0], v = H[i][1];
		adj[u].emplace_back(v, L[i]);
		adj[v].emplace_back(u, L[i]);
	}
	
	int ans = N + 1;
	
	auto dfs = [&](auto &&self, int v, int p, long long pref, int d) -> void {
		mp[pref] = d;
		
		if(pref - K >= 0 && mp.count(pref - K)) {
			ans = min(ans, d - mp[pref - K]);
		}
		
		for(auto [to, w] : adj[v]) {
			if(to == p) continue;
			
			self(self, to, v, pref + w, d + 1);
		}
		
		mp.erase(pref);
	};
	
	dfs(dfs, 0, 0, 0, 0);
	
	return (ans == N + 1 ? -1 : ans);
}

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