| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 882769 | dosts | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define sp << " " <<
#define int long long
#define vi vector<int>
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
#define pii pair<int,int>
const int lim = 2e5+1;
vector<pii> edges[lim];
vi d(lim),dd(lim,-1),dp(lim);
map<int,int> mp[lim];
void dep(int node,int p,int de = 0) {
d[node] = de;
dd[node] = dd[p]+1;
for (auto it : edges[node]) {
if (it.first != p) dep(it.first,node,de+it.second);
}
}
int k;
void dfs(int node,int p) {
mp[node][d[node]] = dd[node];
for (auto it : edges[node]) {
if (it.first == p) continue;
dp[node] = min(dp[node],dp[it.first]);
dfs(it.first,node);
if (mp[it.first].size() > mp[node].size()) mp[node].swap(mp[it.first]);
for (auto itt : mp[it.first]) {
if (mp[node].count(k+2*d[node]-itt.first)) {
dp[node] = min(dp[node],mp[node][k+2*d[node]-itt.first]+itt.second-2*dd[node]);
}
}
for (auto itt : mp[it.first]) {
if (!mp[node].count(itt.first)) mp[node].insert(itt);
else mp[node][itt.first] = min(mp[node][itt.first],itt.second);
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
k = K;
F(i,N-1) edges[H[i-1][0]+1].push_back({H[i-1][1]+1,L[i-1]});
dep(1,1);
dfs(1,1);
return dp[1];
}