| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 681970 | Magikarp4000 | Race (IOI11_race) | C++17 | 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;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n'
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PDD pair<double, double>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;
const int MAXN = 2e5+1, MAXK = 1e6+1;
int n,k;
int h[MAXN][2], l[MAXN];
vector<pair<int,int>> v[MAXN];
int res = INF;
int dp[MAXN];
bool r[MAXN];
vector<UM<int,int>> mp;
UM<int,vector<pair<int,int>>> w;
//APPLEAPPLEAPPLEAPPLEAPPLEAPPLEAPPLEAPPLE BRUH
void dfs(int s,int pa) {
dp[s]++;
FORX(u,w[s]) {
if (u.F == pa || r[u.F]) continue;
dfs(u.F,s);
dp[s] += dp[u.F];
}
}
int decomp(int s, int pa, int cur) {
bool ok = 1;
FORX(u,w[s]) {
if (u.F == pa || r[u.F]) continue;
if (dp[u.F]*2 > cur) {
return decomp(u.F,s,cur);
}
}
return s;
}
void dfs1(int s, int pa, int id, int len, int cnt) {
if (!mp[id].count(len)) mp[id][len] = cnt;
else mp[id][len] = min(mp[id][len], cnt);
FORX(u,w[s]) {
if (u.F == pa || r[u.F] || len+u.S > k) continue;
dfs1(u.F,s,id,len+u.S,cnt+1);
}
}
void dfs2(int s, int pa) {
FORX(u,v[s]) {
if (u.F == pa) continue;
w[u.F].PB({s,u.S});
w[s].PB({u.F,u.S});
dfs2(u.F,s);
}
}
void COUTSUS() {
FORX(u,w) {
cout << u.F << ": ";
FORX(y,u.S) cout << y.F << ' ';
cout << ln;
}
}
void solve(int root) {
FOR(i,0,n) dp[i] = 0;
dfs(root,-1);
int cent = decomp(root,-1,dp[root]);
UM<int,vector<PII>> vw;
FORX(u,w) vw[u.F] = u.S;
int num = 0;
mp.clear();
//FORX(u,mp) FORX(y,u) cout << y.F << " LOL\n";
//cout << cent << ln;
//cout << w[cent].size() << ln;
FORX(u,w[cent]) {
UM<int,int> tmp;
mp.PB(tmp);
dfs1(u.F,cent,num,u.S,1);
num++;
}
UM<int,int> sus;
sus[0] = 0;
FORX(u,mp[0]) {
if (!sus.count(u.F)) sus[u.F] = u.S;
else sus[u.F] = min(sus[u.F],u.S);
if (u.F == k) res = min(res,sus[u.F]);
}
//cout << cent << ln;
FOR(i,1,(int)mp.size()) {
//FORX(u,sus) cout << u.F << ' ' << u.S << ln;
//cout << ln;
FORX(u,mp[i]) {
if (sus.count(k-u.F)) {
// cout << "BRUH " << k-u.F << ' ' << sus[k-u.F] << ln;
res = min(res,sus[k-u.F]+u.S);
// cout << res << ln;
}
if (!sus.count(u.F)) sus[u.F] = u.S;
else sus[u.F] = min(sus[u.F], u.S);
}
}
//COUTSUS();
//cout << ln;
//cout << cent << ln;
FORX(u,vw[cent]) {
w.clear();
dfs2(u.F,cent);
solve(u.F);
}
}
int best_path(int n, int k, int h[][2], int l[]) {
FOR(i,0,n-1) {
v[h[i][0]].PB({h[i][1],l[i]});
}
FOR(i,0,n) {
FORX(u,v[i]) {
w[i].PB({u.F,u.S});
w[u.F].PB({i,u.S});
}
}
solve(0);
return res == INF ? -1 : res;
}
int main() {
OPTM;
cin >> n >> k;
FOR(i,0,n-1) {
cin >> h[i][0] >> h[i][1] >> l[i];
}
cout << best_path(n,k,h,l);
}