| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 915022 | Cabralbonzao | Race (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define N 200010
#define INF 1000000020
#define INFLL 1000000000000000020
#define fi first
#define se second
#define pb push_back
#define LOG 18
#define SQRT 25
typedef long long ll;
typedef pair< int, int > pii;
typedef pair< ll, ll > pll;
typedef vector< ll > vl;
typedef vector< pll > vll;
typedef tuple< int, int, int> tiii;
typedef tuple< ll, ll, ll> tlll;
vector<ll>*vet[N];
ll ans=INFLL;
ll k;
ll sz[N];
ll lvl[N];
ll sum[N];
vector<ll>grafo[N];
map<pll,ll>qtd;
map<pll,ll> :: iterator it;
map<pll,ll>peso;
map<ll,bool>has;
void Verify(ll val)
{
if(!has[val])
{
has[val]=true;
qtd[{val,INFLL}]++;
}
return;
}
void ADD(ll val,ll nivel)
{
Verify(val);
qtd[{val,nivel}]++;
return;
}
void REMOVE(ll val,ll nivel)
{
qtd[{val,nivel}]--;
if(!qtd[{val,nivel}])
{
qtd.erase({val,nivel});
}
return;
}
void build(ll u,ll p)
{
sz[u]=1;
ll w;
for(auto v : grafo[u])
{
if(v==p)
continue;
w=peso[{u,v}];
lvl[v]=lvl[u]+1LL;
sum[v]=sum[u]+w;
build(v,u);
sz[u]+=sz[v];
}
return;
}
void DFS(ll u,ll p,bool keep)
{
ll mx=-1,big;
for(auto v : grafo[u])
{
if(v==p)
continue;
if(mx<sz[v])
{
mx=sz[v];
big=v;
}
}
for(auto v : grafo[u])
{
if(v==p || v==big)
continue;
DFS(v,u,false);
}
if(mx!=-1)
{
DFS(big,u,true);
vet[u]=vet[big];
}else
{
vet[u]=new vector<ll>();
}
ll K=k+2*sum[u];
(*vet[u]).pb(u);
ADD(sum[u],lvl[u]);
for(auto v : grafo[u])
{
if(v==p || v==big)
continue;
for(auto x : (*vet[v]))
{
Verify(K-sum[x]);
it=qtd.lower_bound({K-sum[x],0LL});
ans=min(ans,lvl[x]+
(*it).first.second-
2*lvl[u]);
}
for(auto x : (*vet[v]))
{
(*vet[u]).pb(x);
ADD(sum[x],lvl[x]);
}
}
Verify(k+sum[u]);
it=qtd.lower_bound({k+sum[u],0LL});
ans=min(ans,(*it).first.second-lvl[u]);
if(!keep)
{
for(auto x : (*vet[u]))
{
REMOVE(sum[x],lvl[x]);
}
}
return;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll n,i=0,u,v,w;
cin >> n >> k;
while(i<n-1)
{
cin >> u >> v >> w;
grafo[u].pb(v);
grafo[v].pb(u);
peso[{u,v}]=peso[{v,u}]=w;
i++;
}
i=0;
lvl[0]=1;
build(0,0);
DFS(0,0,true);
if(ans>n)
ans=-1;
cout << ans << endl;
return 0;
}