| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1102538 | seoul_korea | Race (IOI11_race) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const bool multiTest = 0;
#define TASK ""
#define REP(i, n) for(int i = 1; i <= n; i++)
#define FOR(i, a, b) for(auto i = a; i <= b; i++)
#define FORD(i, a, b) for(auto i = a; i >= b; i--)
template<class T> bool maximize(T& a, T b) { if(a < b) return a = b, 1; return 0; }
template<class T> bool minimize(T& a, T b) { if(a > b) return a = b, 1; return 0; }
mt19937 rng(time(0));
const int maxN = (int)2e5 + 7, maxK = (int)1e6 + 7, INF = (int)1e9 + 7;
using ii = pair<int, int>;
int f[maxK], child[maxN];
bool del[maxN];
vector<ii> G[maxN];
vector<int> used;
int numNode, limK;
int getSize(int u, int p = -1) {
child[u] = 1;
for(ii nxt : G[u]) {
int v = nxt.first, w = nxt.second;
if(v == p || del[v]) continue;
child[u] += getSize(v, u);
}
return child[u];
}
int getCentroid(int sz, int u, int p = -1) {
for(ii nxt : G[u]) {
int v = nxt.first;
if(!del[v] && v != p && child[v] > sz) return getCentroid(sz, v, u);
}
return u;
}
int ans = INF;
void calc(int u, bool filling, int dist, int cntEdge, int p = -1) {
if(dist > limK) return;
if(filling) {
minimize(f[dist], cntEdge);
used.push_back(dist);
}
else minimize(ans, f[limK - dist] + cntEdge);
for(ii nxt : G[u]) {
int v = nxt.first, w = nxt.second;
if(del[v] || v == p) continue;
calc(v, filling, dist + w, cntEdge + 1, u);
}
}
void dnc(int x = 1) {
int root = getCentroid(getSize(x) >> 1, x);
//cout << root << endl;
del[root] = 1;
for(ii nxt : G[root]) {
int v = nxt.first, w = nxt.second;
if(del[v]) continue;
calc(v, 0, w, 1);
calc(v, 1, w, 1);
}
for(int d : used) {
f[d] = INF;
}
used.clear();
for(ii nxt : G[root]) {
int v = nxt.first, w = nxt.second;
if(del[v]) continue;
dnc(v);
}
}
void solve(const int& curTest) {
cerr << "\n>TEST #" << curTest << "<\n";
// GET AC PLEASE
cin >> numNode >> limK;
REP(i, numNode - 1) {
int u, v, w;
cin >> u >> v >> w;
u++; v++;
G[u].push_back({v, w});
G[v].push_back({u, w});
}
memset(f, 0x3f, sizeof f);
f[0] = 0;
dnc();
if(ans == INF) {
cout << -1 << endl;
return;
}
cout << ans << endl;
}
signed main() {
cin.tie(0)->ios_base::sync_with_stdio(0);
if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin);
if(fopen(TASK".INP", "r")) {
freopen(TASK".INP", "r", stdin);
freopen(TASK".OUT", "w", stdout);
}
int nTest = 1;
if(multiTest) cin >> nTest;
for(int iTest = 1; iTest <= nTest; iTest++) solve(iTest);
return 0;
}