| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 400193 | MOUF_MAHMALAT | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long ll;
vector<vector<pair<ll,ll> > >v;
ll x,y,ans=1e9,p[200009],k;
bool b[200009];
deque<ll>dq;
map<ll,ll>op;
void dfs(ll d,ll pp)
{
p[d]=1;
for(auto z:v[d])
{
if(z.f==pp||b[z.f])
continue;
dfs(z.f,d);
p[d]+=p[z.f];
}
}
ll center(ll d,ll pp)
{
for(auto z:v[d])
{
if(z.f==pp||b[z.f])
continue;
if(p[z.f]*2>y)
return center(z.f,d);
}
return d;
}
void add(ll d,ll pp,ll sum,ll h)
{
if(sum>k)
return;
if(op[k-sum]||sum==k)
ans=min(ans,op[k-sum]+h);
for(auto z:v[d])
{
if(z.f==pp||b[z.f])
continue;
add(z.f,d,sum+z.s,h+1);
}
if(op[sum])
op[sum]=min(op[sum],h);
else
op[sum]=h;
}
int best_path(ll n, ll K, ll H[][2], ll co[])
{
k=K;
if(k==0)
return 0;
v.resize(n);
for(ll i=0; i<n-1; i++)
{
x=H[i][0], y=H[i][1];
v[x].push_back({y,co[i]});
v[y].push_back({x,co[i]});
}
dq.push_back(0);
while(dq.size())
{
x=dq.front();
dq.pop_front();
dfs(x,-1);
y=p[x];
x=center(x,-1);
op.clear();
b[x]=1;
for(auto z:v[x])
{
if(b[z.f])
continue;
add(z.f,x,z.s,1);
dq.push_back(z.f);
}
}
if(ans==1e9)
ans=-1;
return ans;
}