| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 742235 | beaboss | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define s second
#define f first
#define pb push_back
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<ll> vi;
#define FOR(i, a, b) for (ll i = (a); i<b; i++)
const ll MN = 3e5 + 10;
vpii adj[MN];
ll d[MN]; // from root in highways
ll d2[MN]; // from root in distance
ll k;
void dfs(ll cur = 0, ll dist = 0, ll dist2 = 0, ll p = -1) {
// cout << cur << endl;
d[cur]=dist;
d2[cur]=dist2;
for (auto val: adj[cur]) {
if (val.f != p) {
dfs(val.f, dist + 1, dist2 + val.s, cur);
}
}
}
map<ll, ll> small[MN];
ll ans = 1e9;
void solve(ll cur, ll p=-1) {
for (auto val: adj[cur]) {
if (val.f != p) {
solve(val.f, cur);
// cout << ' ' << val.f << ' ' << cur << d2[cur] << endl;
if (small[val.f].find(k + d2[cur]) != small[val.f].end()) {
// cout << " " << small[val.f][k + d2[cur]] << d[cur] << endl;
ans = min(ans, small[val.f][k + d2[cur]] - d[cur]);
// cout << ans << endl;
}
if (small[val.f].size() > small[cur].size()) swap(small[val.f], small[cur]);
// merge
for (pii nx: small[val.f]) {
if (small[cur].find(k + 2*d2[cur] - nx.f) != small[cur].end()) {
ans = min(ans, small[cur][k + 2*d2[cur] - nx.f] + nx.s - d[cur]);
}
}
for (pii nx: small[val.f]) {
if (small[cur].find(nx.f) == small[cur].end()) small[cur][nx.f]=nx.s;
else small[cur][nx.f]=min(small[cur][nx.f], nx.s);
}
}
}
if (small[cur].find(d2[cur]) == small[cur].end()) small[cur][d2[cur]]=d[cur];
else small[cur][d2[cur]]=min(small[cur][d2[cur]], d[cur]);
// cout << cur << endl;
// for (auto val: small[cur]) {
// cout << val.f << val.s << endl;
// }
}
int best_path(ll N, ll K, ll H[][2], ll L[])
{
k = K;
FOR(i, 0, N-1) {
adj[H[i][0]].pb({H[i][1], L[i]});
}
dfs();
solve(0);
if (ans == 1e9) ans = -1;
return ans;
}