| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 260287 | aggu_01000101 | 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 <iostream>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <bits/stdc++.h>
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define int long long
#define INF 10000000000000000
#define MOD 1000000007
using namespace std;
const int N = 200005;
const int K = 1000005;
vector<pair<int, int>> adj[N];
int tb = 0;
int t = 0;
int tin[N], tout[N];
int depth[N], edges[N];
int h[N][20];
int s[N], size = 0;
int ans = INF;
vector<int> ett;
map<int, int> d;
map<int, bool> vis;
int LCA_DFS(int i, int par, int dep, int edep){
tin[i] = ett.size();
ett.push_back(i);
depth[i] = dep;
edges[i] = edep;
s[i] = 1;
if(i!=par){
h[i][0] = par;
for(int j = 1;j<=19;j++){
if(h[i][j-1] != -1) h[i][j] = h[h[i][j-1]][j-1];
}
}
for(pair<int, int> j: adj[i]){
if(j.first == par) continue;
s[i] += LCA_DFS(j.first, i, dep + j.second, edep+1);
}
tout[i] = ett.size();
return s[i];
}
bool anc(int u, int v){
if((tin[u] <= tin[v]) && (tout[u] >= tout[v])) return true;
return false;
}
int LCA(int u, int v){
if(anc(u, v)){
return u;
}
if(anc(v, u)) return v;
for(int i = 19;i>=0;i--){
if(h[u][i]!=-1 && !anc(h[u][i], v)) u = h[u][i];
}
return h[u][0];
}
pair<int, int> dist(int u, int v){
return {(depth[u] + depth[v] - 2*depth[LCA(u, v)]), (edges[u] + edges[v] - 2*edges[LCA(u, v)])};
}
pair<int, int> dfs(int i, int par, int keep){
pair<int, int> comp = {0, 0};
int bigChild = -1, mx = 0;
for(pair<int, int> j: adj[i]){
if(j.first == par) continue;
if(s[j.first] > mx){
bigChild = j.first;
mx = s[j.first];
}
}
for(pair<int, int> j: adj[i]){
if(j.first == par || j.first == bigChild) continue;
dfs(j.first, i, 0);
}
if(bigChild != -1){
comp = dfs(bigChild, i, 1);
comp.first += dist(bigChild, i).first; //d[x] is actually at d[x - comp.first]
//when we want d[x], we have to try d[x + ]
comp.second++;//d[x] = y actually means d[x] = y + comp.second
}
vis[0 - comp.first] = true;
d[0 - comp.first] = -comp.second;
if(vis[tb - comp.first]) ans = min(ans, d[tb-comp.first] + comp.second);
for(pair<int, int> j: adj[i]){
if(j.first == par || j.first == bigChild) continue;
for(int x = tin[j.first];x<tout[j.first];x++){
pair<int, int> lol = dist(i, ett[x]);
if(lol.first > tb) continue;
if(vis[tb - lol.first - comp.first]) ans = min(ans, d[tb-lol.first-comp.first] + comp.second + lol.second);
}
for(int x = tin[j.first];x<tout[j.first];x++){
pair<int, int> lol = dist(i, ett[x]);
if(lol.first > tb) continue;
if(!vis[lol.first - comp.first]){
vis[lol.first - comp.first] = true;
d[lol.first - comp.first] = lol.second - comp.second;
}
else{
d[lol.first - comp.first] = min(d[lol.first - comp.first], lol.second - comp.second);
}
}
}
if(keep == 0){
d.clear();
vis.clear();
}
return comp;
}
signed best_path(signed n, signed k, signed hh[][2], signed l[]){
tb = k;
ans = INF;
for(int i = 0;i<(n-1);i++){
adj[hh[i][0]+1].push_back({hh[i][1]+1, l[i]});
adj[hh[i][1]+1].push_back({hh[i][0]+1, l[i]});
}
for(int i = 1;i<=n;i++){
for(int j = 0;j<20;j++) h[i][j] = -1;
}
LCA_DFS(1, 1, 0, 0);
dfs(1 ,1 ,0);
if(ans>=INF) ans = -1;
return ans;
}
signed main(){
signed n, k;
cin>>n>>k;
signed bitch[n-1][2];
signed l[n-1];
for(int i =0 ;i<(n-1);i++) cin>>bitch[i][0]>>bitch[i][1]>>l[i];
cout<<best_path(n, k, bitch, l)<<endl;
}
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
*/
/*
3 3
0 1 1
1 2 1
*/