| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 605495 | mychecksedad | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int M = 2e5 + 100;
struct Edge{
int next, len;
};
int n, k, sub[M], best = M;
ll val[M];
vector<Edge> g[M];
map<int, pair<bool, int>> a[M];
void dfs(int v, int p){
int mx = 0, big = -1;
for(Edge e: g[v]){
if(e.next != p && sub[e.next] > mx){
mx = sub[e.next];
big = e.next;
}
}
for(Edge e: g[v]){
if(e.next != p && e.next != big)
dfs(e.next, v);
}
if(big > -1)
dfs(big, v), a[v].swap(a[big]);
if(a[v][val[v]].first == 0){
a[v][val[v]].first = 1;
}else a[v][val[v]].second = 0;
for(Edge e: g[v]){
if(e.next != big && e.next != p){
for(auto p: a[e.next]){
if(a[v][k - p.first + 2 * val[v]].first == 1) best = min(best, p.second.second + a[v][k - p.first + 2 * val[v]].second);
if(a[v][p.first].first == 0){
a[v][p.first] = {1, p.second.second};
}else a[v][val[v]].second = min(a[v][val[v]].second, p.second.second);
}
}
}
}
void init(int v, int p, ll d){
sub[v] = 1;
val[v] = d;
for(Edge e: g[v]){
if(e.next != p){
dfs(e.next, v, d + e.len);
sub[v] += sub[e.next];
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
best = N;
n = N;
k = K;
Edge e;
for(int i = 0; i < n-1; ++i){
e.next = H[i][1];
e.len = L[i];
g[H[i][0]].pb(e);
e.next = H[i][0];
g[H[i][1]].pb(e);
}
init(1, 0, 0);
dfs(1, 0);
return best;
}