| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 413072 | ngpin04 | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "race.h"
#include "grader.cpp"
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int Nmax = 2e5 + 5;
vector <pair <int, int>> adj[Nmax];
map <long long, int> s[Nmax];
long long val[Nmax];
int cnt[Nmax];
int k, ans = 1e9;
void dfs(int u, int p) {
int vmax = u;
for (pair <int, int> e : adj[u]){
int v = e.fi;
int w = e.se;
if (v == p)
continue;
dfs(v, u);
if (s[v].size() > s[vmax].size()) {
vmax = v;
cnt[u] = cnt[vmax] + 1;
val[u] = val[vmax] + w;
}
}
swap(s[u], s[vmax]);
s[u][-val[u]] = -cnt[u];
if (vmax == u)
return;
for (pair <int, int> e : adj[u]) {
int v = e.fi;
int w = e.se;
if (v == vmax)
continue;
for (pair <long long, int> pir : s[v]) {
long long res = k - (pir.fi + val[v] + w) - val[u];
if (s[u].count(res))
ans = min(ans, (s[u][res] + cnt[u]) + (pir.se + cnt[v]) + 1);
}
for (pair <long long, int> pir : s[v]) {
long long res = (pir.fi + val[v] + w) - val[u];
int rescnt = (pir.se + cnt[v] + 1) - cnt[u];
if (!s[u].count(res))
s[u][res] = rescnt;
else
s[u][res] = min(s[u][res], rescnt);
}
}
// cout << "Path " << u << ": \n";
// for (pair <long long, int> pir : s[u])
// cout << pir.fi + val[u] << " " << pir.se + cnt[u] << "\n";
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
for (int i = 0; i < N - 1; i++) {
int u = H[i][0];
int v = H[i][1];
adj[u].push_back(mp(v, L[i]));
adj[v].push_back(mp(u, L[i]));
}
dfs(0, -1);
if (ans == 1e9)
ans = -1;
return ans;
}