제출 #930905

#제출 시각아이디문제언어결과실행 시간메모리
930905Art_ogo경주 (Race) (IOI11_race)C++17
21 / 100
196 ms21972 KiB
#include <bits/stdc++.h> #include "race.h" #define ll long long #define ve vector #define fi first #define se second using namespace std; const int MAXN = 1e5+10; typedef pair<ll, ll> pll; ve<pll> g[MAXN]; int sz[MAXN]; bool del[MAXN]; ve<pll> comp; ll k; void updsz(int v, int p){ sz[v] = 1; for(auto& to : g[v]) if(to.fi != p && !del[to.fi]){ updsz(to.fi, v); sz[v] += sz[to.fi]; } } int centroid(int v, int p, int ssz){ for(auto& to : g[v]) if(to.fi != p && !del[to.fi] && 2*sz[to.fi] > ssz) return centroid(to.fi, v, ssz); return v; } struct vertex{ int sum, len, id; }; void add(int v, int p, int len, int sum){ comp.push_back({sum, len}); for(auto& to : g[v]) if(to.fi != p && !del[to.fi]) add(to.fi, v, len + 1, to.se + sum); } int decomp(int v){ updsz(v, v); int ssz = sz[v]; int res = 1e9; v = centroid(v, v, ssz); del[v] = 1; map<ll, int> mp; mp[0] = 0; for(auto to : g[v]){ if(!del[to.fi]){ comp.clear(); add(to.fi, v, 1, to.se); for(auto i : comp) if(mp.find(k - i.fi) != mp.end()) res = min<int>(res, mp[k - i.fi] + i.se); for(auto i : comp) if(mp.find(i.fi) == mp.end() || mp[i.fi] > i.se) mp[i.fi] = i.se; } } for(auto to : g[v]) if(!del[to.fi]) res = min(res, decomp(to.fi)); return res; } int best_path(int N, int K, int H[][2], int L[]) { k = K; for(int i = 0; i < N - 1; i++){ int u = H[i][0], v = H[i][1], w = L[i]; g[u].push_back({v, w}); g[v].push_back({u, w}); } int res = decomp(0); if(res == 1e9) return -1; return 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...