이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |