| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 728012 | CutSandstone | Race (IOI11_race) | C++11 | 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>
#define ll long long
#define f first
#define s second
#define pb push_back
#define mod 1000000007
#define maxN 200000
using namespace std;
void setio(string name = "") {
ios::sync_with_stdio(false), cin.tie(nullptr);
if(name.length()) {
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
class AddMap {
public:
unordered_map<int, int> mp;
int add1, add2;
AddMap(){
add1 = 0;
add2 = 0;
mp.clear();
}
vector<pair<int, int>> iter(){
vector<pair<int, int>> ret(mp.size());
for(auto i: mp) ret.pb({i.f+add1, i.s+add2});
return ret;
}
int get(int num){
return mp.find(num-add1) == mp.end() ? -1:mp[num-add1]+add2;
}
void put(int num, int val){
mp[num-add1] = val-add2;
}
void addKey(int num){
add1+=num;
}
void addVal(int num){
add2+=num;
}
int size(){
return mp.size();
}
};
int N, K, ans = 1<<30;
vector<pair<int, int>> g[maxN];
AddMap* dfs(int s, int p){
AddMap* ret = new AddMap();
for(pair<int, int> e: g[s]) if(e.f != p){
AddMap* get = dfs(e.f, s);
get->put(0, 0);
get->addKey(e.s);
get->addVal(1);
int up = get->get(K);
if(up != -1) ans = min(ans, up);
if(get->size() > ret->size()){
AddMap* save = get;
get = ret;
ret = save;
}
vector<pair<int, int>> v = get->iter();
for(pair<int, int> c: v){
int curr = ret->get(K-c.f);
if(curr != -1) ans = min(ans, c.s+curr);
}
for(pair<int, int> c: v){
int curr = ret->get(c.f);
if(curr == -1 || curr > c.s) ret->put(c.f, c.s);
}
}
return ret;
}
int main(){
setio();
cin >> N >> K;
for(int i = 1; i<N; i++){
int a, b, c; cin >> a >> b >> c;
g[a].pb({b, c});
g[b].pb({a, c});
}
dfs(0, -1);
if(ans == 1<<30) cout << -1;
else cout << ans;
}