| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 378486 | Gilgamesh | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(),(x).end()
#define pb push_back
const int mxN = 200000;
const int ninf = -1e9;
int k;
vector<array<int, 2>> adj[mxN];
set<array<int, 2>> paths[mxN];
array<int, 2> add[mxN];
int ans = 1e9;
void dfs(int v, int p) {
for(auto[i, w] : adj[v]) {
if(i == p) continue;
dfs(i, v);
add[i][0] += w;
++add[i][1];
if(paths[i].size() > paths[v].size()) {
swap(add[i], add[v]);
paths[v].swap(paths[i]);
}
for(auto[len, edges] : paths[i]) {
int cur = len + add[i][0];
array<int, 2> search = {k - cur - add[v][0], ninf};
auto lb = paths[v].lower_bound(search);
if(lb != paths[v].end() && (*lb)[0] + add[v][0] + cur == k) {
ans = min(ans, edges + (*lb)[1] + add[i][1]);
}
paths[v].insert({len + add[i][0] - add[v][0], edges + add[i][1] - add[v][1]});
}
}
array<int, 2> find = {k - add[v][0], ninf};
auto lb = paths[v].lower_bound(find);
if(lb != paths[v].end() && (*lb)[0] + add[v][0] == k) {
ans = min(ans, (*lb)[1] + add[v][1]);
}
paths[v].insert({0, 0});
}
int best_path(int N, int K, int H[][2], int L[]) {
k = K;
for(int i = 0; i < N - 1; ++i) {
adj[H[i][0]].pb({H[i][1], L[i]});
adj[H[i][1]].pb({H[i][0], L[i]});
}
dfs(0, -1);
return ans == 1e9 ? -1 : ans;
}
/*
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int N, K; cin >> N >> K;
int H[N - 1][2], L[N - 1];
for(int i = 0; i < N - 1; ++i) {
cin >> H[i][0] >> H[i][1];
}
for(int i = 0; i < N - 1; ++i) {
cin >> L[i];
}
cout << best_path(N, K, H, L) << "\n";
}
*/