| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 645847 | Vectorized | 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.
#define ll long long
#define maxN 2000005
using namespace std;
#include <iostream>
#include <iostream>
#include<vector>
#include <climits>
#include<set>
#include<map>
int n;
ll k;
//first = node, second = weight
vector<pair<int ,ll>> adj[maxN];
map<ll, int> sets[maxN];
vector<int> ord;
int p[maxN], lzN[maxN];
ll lzW[maxN];
void dfs(int node, int parent){
p[node] = parent;
for(pair<int, int> j: adj[node]){
if(j.first != parent){
dfs(j.first, node);
ord.push_back(j.first);
}
}
}
int main() {
cin >> n >> k;
for (int i = 0; i < n - 1; ++i) {
int a, b, w;
cin >> a >> b >> w;
adj[a].push_back(make_pair(b, w));
adj[b].push_back(make_pair(a, w));
}
dfs(0, -1);
p[0] = -1;
ord.push_back(0);
int ans = INT_MAX;
for (int i = 0; i < n; ++i) {
int node = ord[i];
if(adj[node].size() == 1 && node != 0){
lzW[node] = 0;
lzN[node] = 0;
continue;
}
int bn = -1, bz = -1;
ll bw = 0;
for(pair<int, int> j : adj[node]){
if(j.first == p[node]) continue;
if((int)sets[j.first].size() > bz){
bz = (int)sets[j.first].size();
bn = j.first;
bw = j.second;
}
}
swap(sets[bn], sets[node]);
lzW[node] = lzW[bn] + bw;
lzN[node] = lzN[bn] + 1;
sets[node][bw - lzW[node]] = 1 - lzN[node];
for(pair<int, int> j: adj[node]){
if(j.first == p[node] || j.first == bn) continue;
for (auto const& a : sets[j.first]){
ll f = k - (a.first + lzW[j.first] + j.second) - lzW[node];
if(sets[node].find(f) != sets[node].end()){
ans = min(ans, a.second + lzN[j.first] + 1 + sets[node][f] + lzN[node]);
}
}
for (auto const& a : sets[j.first]){
ll f = (a.first + lzW[j.first] + j.second) - lzW[node];
if(sets[node].find(f) != sets[node].end()){
sets[node][f] = min(sets[node][f], a.second + lzN[j.first] + 1 - lzN[node]);
}else{
sets[node][f] = a.second + lzN[j.first] + 1 - lzN[node];
}
}
ll f = k - j.second;
if(sets[node].find(f) != sets[node].end()){
ans = min(ans, sets[node][f] + lzN[node] + 1);
}
sets[node][j.second - lzW[node]] = 1 - lzN[node];
}
if(sets[node].find(k - lzW[node]) != sets[node].end()){
ans = min(ans, sets[node][k - lzW[node]] + lzN[node]);
}
}
cout << ans << "\n";
}