Submission #1244323

#TimeUsernameProblemLanguageResultExecution timeMemory
1244323enjeeeff경주 (Race) (IOI11_race)C++17
21 / 100
3094 ms21320 KiB
#include<iostream> #include<vector> #include<map> #include<set> #include"race.h" typedef long long ll; #define vec vector using namespace std; struct Edge { ll to, w; }; ll ans, k; vec<vec<Edge> > adj; vec<ll> deleted, ofLength, usedLengths, s; void find_sizes(ll v, ll p = -1) { s[v] = 1; for (auto &e : adj[v]) if (!deleted[e.to] && e.to != p) { find_sizes(e.to, v); s[v] += s[e.to]; } } ll find_centroid(ll v, ll n, ll p = -1) { for (auto &e : adj[v]) if (!deleted[e.to] && e.to != p && s[e.to] * 2 > n) return find_centroid(e.to, n, v); return v; } void use_dfs(ll v, ll dist, ll dist1 = 1, ll p = -1) { for (auto &e : adj[v]) if (!deleted[e.to] && e.to != p) use_dfs(e.to, dist + e.w, dist1 + 1, v); if (dist > k) return; ans = min(ans, ofLength[k - dist] + dist1); if (dist == k) ans = min(ans, dist1); } void apply_dfs(ll v, ll dist, ll dist1 = 1, ll p = -1) { for (auto &e : adj[v]) if (!deleted[e.to] && e.to != p) apply_dfs(e.to, dist + e.w, dist1 + 1, v); if (dist > k) return; ofLength[dist] = min(ofLength[dist], dist1); usedLengths.push_back(dist); } void divide(ll v = 0) { find_sizes(v); ll cent = find_centroid(v, s[v]); deleted[cent] = 1; for (auto &e : adj[cent]) { use_dfs(e.to, e.w); apply_dfs(e.to, e.w); } for (auto &l : usedLengths) ofLength[l] = 1e9; usedLengths.clear(); for (auto &e : adj[cent]) if (!deleted[e.to]) divide(e.to); } // int main() { // ll n; // cin >> n >> k; // adj.assign(n, {}); // deleted.assign(n, 0); // s.resize(n); // ofLength.assign(k + 1, 1e9); // ans = 1e9; // for (ll i = 0; i < n - 1; i++) { // ll a, b, w; // cin >> a >> b >> w; // adj[a].push_back({b, w}); // adj[b].push_back({a, w}); // } // divide(); // cout << (ans == 1e9 ? -1 : ans) << '\n'; // } int best_path(int N, int K, int H[][2], int L[]) { ll i; k = K; deleted.assign(N, 0); adj.assign(N, {}); s.resize(N); ofLength.assign(K + 1, 1e9); ans = 1e9; for (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]}); } divide(); return (ans == 1e9 ? -1 : ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...