| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 111783 | Mercenary | 경주 (Race) (IOI11_race) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define taskname "TEST"
#define pb push_back
typedef long double ld;
typedef long long ll;
const int maxn = 2e5 + 5;
typedef pair<int,int> tpair;
int n , sz[maxn] , h[maxn] , k;
int res = maxn;
vector<tpair> v[maxn];
unordered_map<ll,int> *vec[maxn];
ll dep[maxn];
void DFS1(int u , int p)
{
sz[u] = 1;
for(tpair c : v[u])
{
if(p == c.first)continue;
h[c.first] = h[u] + 1;
dep[c.first] = dep[u] + c.second;
DFS1(c.first,u);
sz[u] += sz[c.first];
}
}
void add(unordered_map<ll,int> & s , int h1 , ll d1 , int& h , ll& d , int type)
{
if(type == 1)
{
ll need = k - d1 + 2 * d;
if(!s.count(need))return;
res = min(res ,s[need] + h1 - 2 * h);
}
else {
if(!s.count(d1))
{
s[d1] = h1;
return;
}
int tmp = s[d1];
if(tmp > h1)s[d1] = h1;
}
}
void DSU(int u , int p)
{
int bigchild = -1;
for(auto c : v[u])
if(c.first != p && (bigchild == -1 || sz[bigchild] < sz[c.first]))
bigchild = c.first;
for(auto c : v[u])
if(c.first != p && c.first != bigchild)
DSU(c.first , u);
if(bigchild != -1)
{
DSU(bigchild , u);
vec[u] = vec[bigchild];
}
else vec[u] = new unordered_map<ll,int>;
add(*vec[u] , h[u] , dep[u] , h[u] , dep[u] , 0);
add(*vec[u] , h[u] , dep[u] , h[u] , dep[u] , 1);
for(auto c : v[u])
if(c.first != p && c.first != bigchild){
for(auto d : (*vec[c.first]))
add(*vec[u] , d.second , d.first , h[u] , dep[u] , 1);
for(auto d : (*vec[c.first]))
add(*vec[u] , d.second , d.first , h[u] , dep[u] , 0);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen(taskname".INP", "r",stdin);
//freopen(taskname".OUT", "w",stdout);
cin >> n >> k;
for(int i = 1 ; i < n ; ++i)
{
int a , b , c;cin >> a >> b >> c;
++a;++b;
v[a].pb({b,c});
v[b].pb({a,c});
}
DFS1(1 ,0);
DSU(1 ,0);
if(res == maxn)cout << -1;
else cout << res;
}