| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 728016 | CutSandstone | 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>
#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 best_path(int a, int b, vector<vector<int>> h, vector<int> l){
N = a;
K = b;
ans = 1<<30;
for(int i = 0; i<N; i++) g[i].clear();
for(int i = 0; i<N-1; i++){
g[h[i][0]].add({h[i][1], h[i][2]});
g[h[i][1]].add({h[i][0], h[i][2]});
}
dfs(0, -1);
if(ans == 1<<30) return -1;
return ans;
}