| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 706931 | Nhoksocqt1 | 경주 (Race) (IOI11_race) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 200005;
set<ii> G[MAXN];
int sz[MAXN], dp[5 * MAXN], numNode, pathLen;
int dfsSize(int u, int p) {
sz[u] = 1;
for (auto it : G[u]) {
int v(it.fi);
if(v != p)
sz[u] += dfsSize(v, u);
}
return sz[u];
}
int centroid(int u, int p, int nSize) {
for (auto it : G[u]) {
int v(it.fi);
if(v != p && sz[v] > nSize / 2)
return centroid(v, u, nSize);
}
return u;
}
int dfs(int u, int p, int len, int cntNode, vector<ii> &dis) {
if(len > pathLen)
return 1e9+7;
dis.push_back({len, cntNode + 1});
int res = min(int(1e9)+7, cntNode + dp[pathLen - len]);
for (auto it : G[u]) {
int v(it.fi), w(it.se);
if(v != p)
res = min(res, dfs(v, u, len + w, cntNode + 1, dis));
}
return res;
}
int build(int u, int p) {
int nSize = dfsSize(u, p);
int c = centroid(u, p, nSize);
dp[0] = 1;
int res(1e9+7);
vector<int> tmp;
for (auto it : G[c]) {
vector<ii> tmpn;
int v(it.fi), w(it.se);
res = min(res, dfs(v, c, w, 1, tmpn));
while(tmpn.size()) {
tmp.push_back(tmpn.back().fi);
minimize(dp[tmp.back()], tmpn.back().se);
tmpn.pop_back();
}
}
for (int it = 0; it < int(tmp.size()); ++it) {
int x(tmp[it]);
dp[x] = 1e9+7;
}
vector<ii> tmpg(G[c].begin(), G[c].end());
for (int it = 0; it < int(tmpg.size()); ++it) {
int v(tmpg[it].fi), w(tmpg[it].se);
G[c].erase({v, w});
G[v].erase({c, w});
res = min(res, build(v, c));
}
return res;
}
void process() {
cin >> numNode >> pathLen;
for (int i = 1; i < numNode; ++i) {
int u, v, w;
cin >> u >> v >> w;
G[u].insert({v, w});
G[v].insert({u, w});
}
for (int i = 0; i <= pathLen; ++i)
dp[i] = 1e9+7;
int res = build(0, -1);
cout << (res >= 1e9 ? -1 : res - 1) << '\n';
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("RACE.inp", "r", stdin);
// freopen("RACE.out", "w", stdout);
process();
return 0;
}