제출 #466576

#제출 시각아이디문제언어결과실행 시간메모리
466576dattranxxx경주 (Race) (IOI11_race)C++11
21 / 100
3076 ms18484 KiB
#include "race.h" /* * Author : shora */ #include <bits/stdc++.h> #define print(_v) for (auto &_ : _v) {cerr << _ << ' ';} cerr << endl; using namespace std; using ll = long long; const int oo = 1e9; const int N = 5e5; struct C { int v, w; C(int v, int w): v(v), w(w) {} }; vector<C> G[N]; int dep[N]; int n, k; int res = oo; void dfs(int u, int e = -1, int dis = 0) { if (k < dis) return; if (e != -1) dep[u] = dep[e] + 1; else dep[u] = 0; if (dis == k) res = min(res, dep[u]); for (C& c : G[u]) if (c.v != e) { dfs(c.v, u, dis + c.w); } } int best_path(int n, int K, int H[][2], int L[]) { k = K; for (int i = 0, u, v, w; i < n-1; ++i) { u = H[i][0]; v = H[i][1]; w = L[i]; G[u].push_back(C(v, w)); G[v].push_back(C(u, w)); } for (int i = 0; i < n; ++i) dfs(i); return res == oo ? -1 : res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...