Submission #618661

#TimeUsernameProblemLanguageResultExecution timeMemory
618661Mohammed_AtalahRace (IOI11_race)C++17
21 / 100
3068 ms18252 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; vector<vector<vector<int>>> edg; int curr = 0; int r = 0; int mn = 1e9; bool found = 0; int k; vector<int> vis; void dfs(int idx) { if (curr == k) { mn = min(r, mn); found = 1; return; } for (auto &i : edg[idx]) { if (!vis[i[0]]) { vis[i[0]] = 1; curr += i[1]; r++; dfs(i[0]); r--; curr -= i[1]; vis[i[0]] = 0; } } } int best_path(int N, int K, int H[][2], int L[]) { k = K; edg.resize(N); vis.resize(N); for (int i = 0 ; i < N - 1; i++) { edg[H[i][0]].push_back({H[i][1], L[i]}); edg[H[i][1]].push_back({H[i][0], L[i]}); } for (int i = 0; i < N; i++) { vis[i] = 1; dfs(i); vis[i] = 0; } return ((found) ? mn : -1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...