| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1108297 | SteveBro | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int mat[200001][2],ll[200001],p;
const int inf=1e9;
struct ura
{
int t,s;
bool ok;
}v[200001];
vector < pair<int,int> > g[200001];
int dfs(int nod, int n)
{
int sol;
bool ok=true;
v[nod].s=1;
for(auto x : g[nod])
{
if(!v[x.first].ok&&v[nod].t!=x.first)
{
v[x.first].t=nod;
sol=dfs(x.first,n);
if(sol!=-1)
return sol;
v[nod].s+=v[x.first].s;
if(v[x.first].s>n/2)
ok=false;
}
}
if(n-v[nod].s>n/2)
ok=false;
if(ok)
return nod;
return -1;
}
unordered_map <long long,int> maph;
std :: unordered_map <long long,int> :: iterator it;
int rez=inf;
void dfs1(int nod, long long d, int nrm)
{
it=maph.find(p-d);
if(it!=maph.end())
rez=min(rez,(*it).second+nrm);
for(auto x : g[nod])
{
if(!v[x.first].ok&&x.first!=v[nod].t)
{
v[x.first].t=nod;
dfs1(x.first,d+x.second,nrm+1);
}
}
}
void dfs2(int nod, long long d, int nrm)
{
it=maph.find(d);
if(it==maph.end())
maph.insert(make_pair(d,nrm));
else
maph.at(d)=min(maph.at(d),nrm);
for(auto x : g[nod])
{
if(!v[x.first].ok&&x.first!=v[nod].t)
{
v[x.first].t=nod;
dfs1(x.first,d+x.second,nrm+1);
}
}
}
void divide(int nod, int nr)
{
if(nr==1)
return;
maph.clear();
int ctd=dfs(nod,nr);
for(auto x : g[ctd])
{
if(!v[x.first].ok)
{
v[x.first].t=ctd;
dfs1(x.first,x.second,1);
dfs2(x.first,x.second,1);
}
}
v[ctd].ok=true;
for(auto x : g[ctd])
{
if(!v[x.first].ok)
{
v[x.first].t=ctd;
divide(x.first,v[x.first].s);
}
}
}
int best_path(int n,int k,int h[200001][2],int l[200001])
{
int i;
for(i=0;i<n-1;i++)
{
g[h[i][0]].push_back(make_pair(h[i][1],l[i]));
g[h[i][1]].push_back(make_pair(h[i][0],l[i]));
}
p=k;
v[1].t=n;
divide(1,n);
if(rez==inf)
rez=-1;
return rez;
}
int main()
{
int n,i,k;
cin>>n>>k;
for(i=0;i<n-1;i++)
{
cin>>mat[i][0]>>mat[i][1];
}
for(i=0;i<n-1;i++)
cin>>ll[i];
cout<<best_path(n,k,mat,ll);
return 0;
}