| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 292464 | davooddkareshki | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair
const int maxn = 2e5+10;
const ll inf = 1e18+10;
const int mod = 1e9+7;
const int N = 2e7+10;
int K;
map<int,int> *mp[maxn];
int st[maxn], h[maxn], sum[maxn];
vector<pii> g[maxn];
void pfs(int v, int p = -1)
{
st[v] = 1;
for(auto e : g[v])
{
int u = e.F, w = e.S;
if(u != p)
{
sum[u] = sum[v] + w;
h[u] = h[v] + 1;
pfs(u,v);
st[v] += st[u];
}
}
}
ll ans = inf;
void dfs(int v, int p = -1)
{
int big = -1;
for(auto e : g[v])
{
int u = e.F;
if(u != p)
{
dfs(u,v);
if(big == -1) big = u;
else if(st[u] > st[big]) big = u;
}
}
if(big != -1) mp[v] = mp[big];
else mp[v] = new map<int,int>;
(*mp[v])[sum[v]] = h[v];
if((*mp[v]).count(K+sum[v]))
ans = min(ans, (*mp[v])[K+sum[v]] - h[v]);
for(auto e : g[v])
{
int u = e.F, w = e.S;
if(u != p && u != big)
{
for(auto X : (*mp[u]))
{
int sm = X.F, Mn = X.S;
if((*mp[v]).count(K-sm+2*sum[v]))
{
int road = Mn + (*mp[v])[K-sm] - 2 * h[v];
ans = min(ans,road);
}
}
for(auto X : (*mp[u]))
{
int sm = X.F, Mn = X.S;
if(!(*mp[v]).count(sm)) (*mp[v])[sm] = Mn;
else (*mp[v])[sm] = min((*mp[v])[sm], Mn);
}
}
}
}
int best_path(int n, int k, int h[][2], int l[])
{
//cin>> n >> K;
K = k;
for(int i = 0, u, v, w; i < n-1; i++)
{
//cin>> u >> v >> w;
u = h[i][0], v = h[i][1], w = l[i];
u++; v++;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
pfs(1); dfs(1);
if(ans == inf) return -1;
else return ans;
}