| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 403019 | Newtech66 | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "race.h"
#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
vector<vector<pair<int,int> > > g(MAXN);
vector<int> subsz(MAXN);
bitset<MAXN> del;
int ans=INT_MAX;
void findsubsz(int u,int p=-1)
{
subsz[u]=1;
for(auto ch:g[u])
{
if(ch.first!=p && !del.test(ch.first))
{
findsubsz(ch.first,u);
subsz[u]+=subsz[ch.first];
}
}
}
void place(map<int,deque<pair<int,int> > > &m,int len,int nm,int u)
{
if(m.find(len)==m.end())
{
m[len].emplace_back(nm,u);
}else if(m[len].size()==1)
{
if(nm<=m[len][0].first)
{
m[len].emplace_front(nm,u);
}else
{
m[len].emplace_back(nm,u);
}
}else
{
if(nm<=m[len][0].first)
{
m[len].pop_back();
m[len].emplace_front(nm,u);
}else if(nm<=m[len][1].first)
{
m[len].pop_back();
m[len].emplace_back(nm,u);
}
}
}
void solve(int u,map<int,set<pair<int,int> > > &m,int len,int dep,int K,int z=-1,int p=-1)
{
for(auto ch:g[u])
{
if(ch.first!=p && !del.test(ch.first))
{
if(len+ch.second<=K)
{
if(p==-1) z=ch.first;
m[len+ch.second].emplace(dep+1,z);
solve(ch.first,m,len+ch.second,dep+1,K,z,u);
}
}
}
}
int getcen(int u,int sz,int p=-1)
{
for(auto ch:g[u])
{
if(!del.test(ch.first) && ch.first!=p)
{
if(2*subsz[ch.first]>sz)
{
return getcen(ch.first,sz,u);
}
}
}
return u;
}
void cendcmp(int u,const int& K)
{
//cout<<u<<endl;
findsubsz(u);
int C=getcen(u,subsz[u]);
//cout<<"Centroid found "<<u<<endl;
map<int,set<pair<int,int> > > m;
solve(C,m,0,0,K);
/*for(auto p:m)
{
cout<<p.first<<": ";
for(auto e:p.second)
{
cout<<"("<<e.first<<","<<e.second<<") ";
}
cout<<endl;
}*/
if(m.find(K)!=m.end()) ans=min(ans,m[K].begin()->first);
for(auto p:m)
{
int len=p.first,nm=p.second.begin()->first,ch=p.second.begin()->second;
if(m.find(K-len)!=m.end())
{
if(m[K-len].begin()->second!=ch)
{
ans=min(ans,nm+m[K-len].begin()->first);
}else
{
if(m[K-len].size()==2)
{
ans=min(ans,nm+(++m[K-len].begin())->first);
}
}
}
}
del.flip(u);
for(auto ch:g[u])
{
if(!del.test(ch.first))
{
cendcmp(ch.first,K);
}
}
}
int best_path(int N, int K, int H[][2], int L[])
{
for(int i=0;i<N-1;i++)
{
int u=H[i][0],v=H[i][1];
g[u].push_back({v,L[i]});
g[v].push_back({u,L[i]});
}
cendcmp(0,K);
if(ans==INT_MAX) return -1;
else return ans;
}
int main()
{
int N,K,H[MAXN][2],L[MAXN];
cin>>N>>K;
for(int i=0;i<N-1;i++)
{
cin>>H[i][0]>>H[i][1]>>L[i];
}
best_path(N,K,H,L);
if(ans==INT_MAX) cout<<-1;
else cout<<ans;
return 0;
}