| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 728012 | CutSandstone | 경주 (Race) (IOI11_race) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}