제출 #864942

#제출 시각아이디문제언어결과실행 시간메모리
864942nasir_bashirov경주 (Race) (IOI11_race)C++11
0 / 100
3 ms14940 KiB
#include <bits/stdc++.h> #include "race.h" using namespace std; #define db long double #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define vi vector<int> #define vl vector<ll> #define vii vector<pii> #define vll vector<pll> #define endl '\n' #define all(x) x.begin(), x.end() #define fastio\ ios_base::sync_with_stdio(0);\ cin.tie(0);\ cout.tie(0)\ const int sz = 2e5 + 5; vll g[sz]; ll n, k, h[sz], res = 1e9; vl v[sz]; set<pll> dfs(ll node, ll par, ll w){ h[node] = h[par] + 1; set<pll> st; for(pll i : g[node]){ if(i.first == par) continue; set<pll> temp = dfs(i.first, node, i.second); if(temp.size() > st.size()) swap(st, temp); for(pll j : temp){ auto it = st.lower_bound({k - j.first, 0}); if(it != st.end() and j.first + (*it).first == k) res = min(res, j.second + (*it).second - 2 * h[node]); } for(pll j : temp){ st.insert(j); } } set<pll> fnl; for(pll i : st){ if(i.first == k) res = min(res, i.second - h[node]); fnl.insert({i.first + w, i.second}); } if(fnl.empty()){ fnl.insert({w, h[node]}); } return fnl; } int best_path(int N, int K, int H[][2], int L[]){ n = N, k = K; for(int i = 0; i < n; i++){ g[H[i][0]].push_back({H[i][1], L[i]}); g[H[i][1]].push_back({H[i][0], L[i]}); } h[0] = -1; dfs(0, 0, 0); res = (res == 1e9 ? -1 : res); 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...