제출 #864378

#제출 시각아이디문제언어결과실행 시간메모리
864378nasir_bashirov경주 (Race) (IOI11_race)C++11
0 / 100
2 ms9560 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; vii g[sz]; int n, k, h[sz], res = 1e9; set<pii> st; map<int, multiset<int>> mp; void preCalc(int node, int par, int c){ h[node] = h[par] + 1; mp[c].insert(h[node]); for(pii i : g[node]){ if(i.first == par) continue; preCalc(i.first, node, c + i.second); } } void deletePath(int node, int par, int c){ mp[c].erase(mp[c].find(h[node])); for(pii i : g[node]){ if(i.first == par) continue; deletePath(i.first, node, c + i.second); } } void insertPath(int node, int par, int c){ mp[c].insert(h[node]); for(pii i : g[node]){ if(i.first == par) continue; insertPath(i.first, node, c + i.second); } } void dfs(int node, int par, int c){ if(c == k) res = min(res, h[node]); st.insert({c, h[node]}); if(c < k and mp[k - c].size()) res = min(res, h[node] + (*mp[k - c].begin())); if(c > k){ auto it = st.lower_bound({c - k, 0}); if(it != st.end()) res = min(res, h[node] - (*it).second); } st.insert({c, h[node]}); for(pii i : g[node]){ if(i.first == par) continue; if(node == 0) deletePath(i.first, node, c + i.second); st.clear(); dfs(i.first, node, c + i.second); if(node == 0) insertPath(i.first, node, c + i.second); } } 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]}); } preCalc(0, 0, 0); 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...