| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1105946 | _hoanglong_ | 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.
// https://oj.vnoi.info/problem/lqdrace
#pragma GCC optimize("O3") // optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
typedef long long ll; // double long double
const ll mod = 1000000007; // 998244353 1000000009 1000000007 // đừng dùng ull
#define int long long // __int128
const int INF = std::numeric_limits<int>::max(); // INT32_MAX DBL_MAX
using namespace std;
#ifdef DEBUG
#include "debug.cpp"
#else
#define dbg(...)
#endif
int k;
struct CentroidDecomposition{
private:
int n;
vector<vector<pair<int,int>>> g;
vector<bool> removed;
// hàm này tính số childNum sau khi đã xóa centroid
int cal_childNum(int root, int parent){
childNum[root] = 1;
for (auto [v, w]: g[root]) {
if (removed[v]) continue;
if (v != parent)
childNum[root] += cal_childNum(v, root);
}
return childNum[root];
}
// check xem u có phải là centroid không, nếu không check node bên cạnh
int get_centroid(int u, int p, int n){
for (auto&[v, w]: g[u]) {
if (removed[v]) continue;
if (v != p)
if (childNum[v] >= n/2)
return get_centroid(v, u, n);
}
return u;
}
void decompose(int u, int c){
int size_subTree = cal_childNum(u, c) + 1;
int sub_centroid = get_centroid(u, u, size_subTree);
parent[sub_centroid] = c;
resolve_centroid(sub_centroid);
removed[sub_centroid] = true;
for (auto&[v, w]: g[sub_centroid]){
if (!removed[v]) decompose(v, sub_centroid);
}
}
public:
vector<int> parent; // thể hiện centroid tree
vector<int> childNum;
int ans = INF/2;
CentroidDecomposition(vector<vector<pair<int,int>>>& g) {
n = g.size();
this->g = g;
parent.assign(n, -1);
childNum.assign(n, 0);
removed.assign(n, false);
// initial calls
decompose(0, -1); // return parent[] - centroid tree
}
// Dạng bài xử lý cho từng điểm và dùng centroid tree để giảm số lần duyệt đồ thị - xử lý khi decompose tree
void resolve_centroid(int sub_centroid) {
// Xử lý từng nhánh 1 xung quanh sub_centroid
map<int, int> data; // data[len_based_on_weight] = node_number
map<int, int> branch; // lưu dữ liệu của từng nhánh khi duyệt
std::function<void(int, int, int, int)> dfs = [&](int u, int p, int weight, int depth) {
if (weight > k) return;
if (branch.find(weight) == branch.end())
branch[weight] = depth;
else
branch[weight] = min(branch[weight], depth);
for (auto&[v, w]: g[u]) {
if (v == p || removed[v]) continue;
dfs(v, u, weight + w, depth+1);
}
};
for (auto&[v, w]: g[sub_centroid]) {
if (removed[v]) continue;
dfs(v, sub_centroid, w, 1);
// Check branch hiện tại kết hợp với các branch khác có tạo ra độ dài K ko
for (auto&[weight, depth]: branch) {
// Kết hợp với các branch khác
if (data.find(k - weight) != data.end()) {
ans = min(ans, depth + data[k-weight]);
}
// Chính branch này chứa kết quả
if (weight == k)
ans = min(ans, depth);
}
// Merge branch hiện tại với data
for (auto&[weight, depth]: branch) {
if (data.find(weight) == data.end())
data[weight] = depth;
else
data[weight] = min(data[weight], depth);
}
branch.clear();
}
}
};
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cout << std::fixed << setprecision(15);
#ifdef DEBUG
freopen("inp.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int n;
cin >>n >> k;
vector<vector<pair<int,int>>> g(n);
for (int i=0;i<n-1;i++) {
int u, v,w;
cin >> u >>v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
CentroidDecomposition cd(g);
cout << ((cd.ans == INF/2) ? (-1) : cd.ans);
cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s✅\n";
}
/*
Race (IOI 2011)
Cho 1 tree N đỉnh có trọng số và 1 số K.
Tìm độ dài đường đi qua số node ít nhất có độ dài K. In ra số lượng cạnh cần phải đi đó
=> Sử dụng centroid tree. Với mỗi centroid ta sẽ tìm ra đường đi ngắn nhất độ dài K qua centroid đó
*/