Submission #1236719

#TimeUsernameProblemLanguageResultExecution timeMemory
1236719nickolasarapidisRace (IOI11_race)C++20
100 / 100
347 ms79720 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define F first #define S second const int MAXN = 200000; int k, ans = MAXN + 5; vector<pair<int, int>> adj[MAXN]; map<int, int> m[MAXN]; void dfs(int s, int e, int d1, int d2){ m[s][d2] = d1; for(auto a : adj[s]){ int u = a.F, w = a.S; if(u == e) continue; dfs(u, s, d1 + 1, d2 + w); if(m[u].size() > m[s].size()) swap(m[u], m[s]); for(auto x : m[u]){ if(m[s].count(2*d2 + k - x.F)) ans = min(ans, m[s][2*d2 + k - x.F] + x.S - 2*d1); } for(auto x : m[u]){ if(m[s].count(x.F)) m[s][x.F] = min(m[s][x.F], x.S); else m[s][x.F] = x.S; } } } int best_path(int N, int K, int H[][2], int L[]){ for(int i = 0; i < N - 1; i++){ adj[H[i][0]].push_back({H[i][1], L[i]}); adj[H[i][1]].push_back({H[i][0], L[i]}); } k = K; dfs(0, -1, 0, 0); if(ans != MAXN + 5) return ans; return -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...