| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1126484 | AIF_is_carving | Race (IOI11_race) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxN = 200010;
vector<pair<int, int>> graph[maxN];
vector<bool> is_removed(maxN, 0);
vector<int> subtree_size(maxN, 0);
vector<LL> pathsize(maxN, 0);
vector<int> depth(maxN, 0);
LL ans = 1e16;
int k;
int get_subtree_size(int node, int parent = -1) {
subtree_size[node] = 1;
for (auto child : graph[node]) {
if (child.first == parent || is_removed[child.first]) { continue; }
subtree_size[node] += get_subtree_size(child.first, node);
}
return subtree_size[node];
}
int get_centroid(int node, int tree_size, int parent = -1) {
for (auto child : graph[node]) {
if (child.first == parent || is_removed[child.first]) { continue; }
if (subtree_size[child.first] * 2 > tree_size) {
return get_centroid(child.first, tree_size, node);
}
}
return node;
}
void dfs(int v, int parent, map<int, int> &m){
for(auto u: graph[v]){
if(u.first!= parent && !is_removed[u.first]){
//cout<<u.first<<" ";
pathsize[u.first] = pathsize[v] + 1LL*u.second;
depth[u.first] = depth[v] +1;
if(m.find(pathsize[u.first]) == m.end()) m[pathsize[u.first]] = depth[u.first];
else m[pathsize[u.first]] = min(depth[u.first], m[pathsize[u.first]]);
dfs(u.first, v, m);
}
}
}
/** Build up the centroid decomposition recursively */
void build_centroid_decomp(int node = 0) {
int centroid = get_centroid(node, get_subtree_size(node));
//cout<<centroid<<" -> "<<"\n";
// do something
map<LL, vector<pair<int, int>> > pathlist;
for(auto child : graph[centroid]){
if(!is_removed[child.first]){
map<LL, int> m;
depth[child.first] = 1;
pathsize[child.first] = 1LL*child.second;
m[pathsize[child.first]] = depth[child.first];
dfs(child.first, centroid, m);
//cout<<"x\n";
for(auto p: m){
pathlist[p.first].push_back({p.second,child.first});
}
}
}
auto it = pathlist.begin();
for(; it != pathlist.end(); it++){
sort((*it).second.begin(), (*it).second.end());
}
for(auto p: pathlist){
int vertice = (p.second)[0].second;
int length = (p.second)[0].first;
//cout<<vertice<<" "<<length<<"\n";
if(pathlist.find(k - p.first) != pathlist.end()){
int nextvertice = pathlist[k - p.first][0].second;
int nextlength = pathlist[k - p.first][0].first;
if(vertice == nextvertice){
if(pathlist[k-p.first].size() == 1) continue;
nextvertice = pathlist[k - p.first][1].second;
nextlength = pathlist[k - p.first][1].first;
}
ans = min(ans, length + nextlength);
}
}
if(pathlist.find(k) != pathlist.end()){
ans = min(ans, pathlist[k][0].first);
}
is_removed[centroid] = true;
for (auto child : graph[centroid]) {
if (is_removed[child.first]) { continue; }
build_centroid_decomp(child.first);
}
}
int best_path(int N, int K, int h[][2], int L[]){
ans = 1e9;
int n = N;
k = K;
for(int i = 0; i<n-1; i++){
graph[h[i][0]].push_back({h[i][1], L[i]});
graph[h[i][1]].push_back({h[i][0], L[i]});
}
build_centroid_decomp(0);
if(ans > 1e8) ans = -1;
return ans;
}