제출 #899945

#제출 시각아이디문제언어결과실행 시간메모리
899945Macker경주 (Race) (IOI11_race)C++17
43 / 100
3037 ms174416 KiB
#include "race.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define all(v) v.begin(), v.end() #pragma GCC optimize("Ofast") #pragma GCC target("avx2") vector<vector<pair<int, int>>> adj; int k; pair<multiset<pair<int, int>>, int> dfs(int a, int p){ multiset<pair<int, int>> cur; cur.insert({0, 0}); int res = INT_MAX; vector<vector<pair<int, int>>> ch; vector<int> mn; if(k < 1000) mn.assign(k + 1, INT_MAX); for (auto [b, c] : adj[a]) { if(b == p) continue; ch.push_back({}); auto [s, x] = dfs(b, a); res = min(res, x); for (auto &i : s) { if(i.first + c > k) continue; ch.back().push_back({i.first + c, i.second + 1}); if(k < 1000) mn[i.first + c] = min(mn[i.first + c], i.second + 1); } } for (auto &&i : ch) for (auto &&j : i){ if(k >= 1000 || j.second == mn[j.first]) cur.insert(j); } for (auto &&i : ch) { for (auto &&j : i){ if(k >= 1000 || j.second == mn[j.first]) cur.erase(cur.find(j)); } for (auto &&j : i) { if(k < 1000 && j.second != mn[j.first]) continue; if(cur.lower_bound({k - j.first, 0}) == cur.end()) continue; pair<int, int> x = *cur.lower_bound({k - j.first, 0}); if(x.first == k - j.first){ res = min(res, x.second + j.second); } } for (auto &&j : i){ if(k >= 1000 || j.second == mn[j.first]) cur.insert(j); } } return {cur, res}; } int best_path(int N, int K, int H[][2], int L[]) { k = K; adj.assign(N, {}); for (int 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]}); } int ret = dfs(0, 0).second; if(ret == INT_MAX) return -1; return ret; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...