| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1126304 | 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 = 20010;
vector<pair<int, int>> graph[maxN];
vector<bool> is_removed(maxN, 0);
vector<int> subtree_size(maxN, 0);
vector<int> pathsize(maxN, 0);
vector<int> depth(maxN, 0);
int ans = 1e9;
int k;
#define MAX_N 500000
static int N, K;
static int H[MAX_N][2];
static int L[MAX_N];
static int solution;
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]){
pathsize[u.first] = pathsize[v] + 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]]);
}
}
}
/** Build up the centroid decomposition recursively */
void build_centroid_decomp(int node = 0) {
int centroid = get_centroid(node, get_subtree_size(node));
// do something
// pathsize[centroid] = 0;
map<int, vector<pair<int, int>> > pathlist;
//cout<<centroid<<" : \n";
for(auto child : graph[centroid]){
map<int, int> m;
depth[child.first] = 1;
pathsize[child.first] = child.second;
m[pathsize[child.first]] = depth[child.first];
dfs(child.first, centroid, m);
for(auto p: m){
//cout<<p.first<<" "<<p.second<<"\n";
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;
if(pathlist.find(k - length) != pathlist.end()){
int nextvertice = pathlist[k - length][0].second;
int nextlength = pathlist[k - length][0].first;
if(vertice == nextvertice){
if(pathlist[k-length].size() == 1) continue;
nextvertice = pathlist[k - length][1].second;
nextlength = pathlist[k - length][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);
}
}