| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 671394 | BreakOfDawn | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Onegai no bug
// Author : 13minusone
#include<bits/stdc++.h>
using namespace std;
#define task "test"
#define SZ(c) (c).size()
#define getbit(x,i) (((x) >> (i)) & 1)
#define turnoff(x,i) (x)&(~(1<<(i)))
#define __builtin_popcount __builtin_popcountll
#define all(x) (x).begin(),(x).end()
#define pb(x) push_back(x)
#define eb(x) emplace_back(x)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define fi first
#define se second
#define FOR(i,l,r) for(int i = l ; i <= r ; i++)
#define FD(i,l,r) for(int i = l ; i >= r ; i--)
#define REP(i,l,r) for(int i = l ; i <r ; i++)
typedef long long ll ;
typedef pair<int,int> ii;
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b),1 : 0); }
template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b),1 : 0); }
const int N = 1e6+ 5;
//const ll MOD =1e17+9;
//const ll base = 311;
//const int BLOCK = 488;
const int INF = 1e9 + 7;
int n, k, sz[N], cnt = 0, ans = INF, pos[N], num[N];
vector<ii>edge[N];
bool vis[N];
void dfs(int u, int pre, int t, int depth, int node, vector<ii>&tmp)
{
if(depth > k)return;
if(depth <= k)
{
if(pos[k - depth] == t)minimize(ans, node + num[k - depth]);
tmp.pb(ii(depth, node));
}
for(ii &v : edge[u])if(v.fi != pre && !vis[v.fi])
dfs(v.fi, u, t, depth + v.se, node + 1, tmp);
}
int getSZ(int u, int pre)
{
if(vis[u])return 0;
sz[u] = 1;
for(ii &v : edge[u])if(v.fi != pre && !vis[v.fi])
{
sz[u] += getSZ(v.fi, u);
}
return sz[u];
}
int getCentroid(int u, int Sizetree, int p)
{
for(ii &v : edge[u])
if(v.fi != p && !vis[v.fi] && sz[v.fi] * 2 > Sizetree)
return getCentroid(v.fi,Sizetree, u);
return u;
}
void CreateCentroid(int u, int pre)
{
u = getCentroid(u, getSZ(u, -1), -1);
vis[u] = 1;
//cout << u << " " << pre << endl;
pos[0] = ++cnt;
num[0] = 1;
for(ii &v : edge[u])if(v.fi != pre && !vis[v.fi])
{
vector<ii>tmp;
dfs(v.fi,u,cnt,v.se,1,tmp);
for(ii &i : tmp)
{
if(pos[i.fi] != cnt)
{
pos[i.fi] = cnt;
num[i.fi] = i.se;
}
else minimize(num[i.fi], i.se);
}
}
for(ii &v : edge[u])if(v.fi != pre && !vis[v.fi])
CreateCentroid(v.fi, u);
}
void init(void)
{
cin >> n >> k;
FOR(i,1,n-1)
{
register int u, v,w;
cin >> u >> v >> w;
edge[u].pb(ii(v,w));
edge[v].pb(ii(u,w));
}
}
void process(void)
{
CreateCentroid(0,-1);
if(k == 0)cout << 1;
else if(ans != INF)cout << ans;
else cout << -1;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--)
{
init();
process();
}
//cerr << "TIME : " << TIME << "s\n";
}