| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 876031 | Zian_Jacobson | 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.
#include<bits/stdc++.h>
using namespace std;
#define cIO ios_base::sync_with_stdio(0);cin.tie(0)
#define fileIO(x) ifstream fin(string(x)+".in"); ofstream fout(string(x)+".out")
#define cont(container, object) (container.find(object)!=container.end())
#define sz(x) (int) (x).size()
#define ll long long
#define v vector
#include "race.h"
const int INF = 1e9;
vector<vector<pair<int,int>>> adj;
vector<int> subtree_size;
// min_dist[v] := the minimal distance between v and a red node
//vector<int> min_dist;
vector<bool> is_removed;
//vector<vector<pair<int, int>>> ancestors;
int get_subtree_size(int node, int parent = -1) {
subtree_size[node] = 1;
for ( auto childn: adj[node]) {
if (childn.first == parent || is_removed[childn.first]) { continue; }
subtree_size[node] += get_subtree_size(childn.first, node);
}
return subtree_size[node];
}
int get_centroid(int node, int tree_size, int parent = -1) {
for (auto childn : adj[node]) {
if (childn.first == parent || is_removed[childn.first]) { continue; }
if (subtree_size[childn.first] * 2 > tree_size) {
return get_centroid(childn.first, tree_size, node);
}
}
return node;
}
/**
* Calculate the distance between current `node` and the `centroid` it belongs
* to. The distances between a node and all its centroid ancestors are stored
* in the vector `ancestors`.
* @param cur_dist the distance between `node` and `centroid`
*/
//
//void build_centroid_decomp(int node = 0) {
// int centroid = get_centroid(node, get_subtree_size(node));
//
// /*
// * For all nodes in the subtree rooted at `centroid`, calculate their
// * distances to the centroid
// */
//
// is_removed[centroid] = true;
// for (int child : adj[centroid]) {
// if (is_removed[child]) { continue; }
// // build the centroid decomposition for all child components
// build_centroid_decomp(child);
// }
//}
map<int,int> dfs_L(int node, int par = -1)
{
map<int, int> res;
res.emplace(0, 0);//highway lengths, minimum segments
for (auto cn : adj[node])
{
int child = cn.first, len = cn.second;
if (!is_removed[child] && child != par)
{
map<int, int> prev = dfs_L(child, node);
for (pair<int, int> x : prev)
{
if (cont(res, x.first + len)) res[x.first + len] = min(res[x.first + len], x.second + 1);
else res.emplace(x.first + len, x.second + 1);
}
}
}
return res;
}
int compute(int node, int K, int par=-1)//does it for the current and child centroids; returns min_roads
{
int min_roads = INF;
node = get_centroid(node, get_subtree_size(node));
map<int, pair<pair<int,int>, pair<int,int>>> lens;// the pairs store the {1st lowest segs used, rep child node} and the 2nd
lens.insert({ 0, { {0, node}, {INF, -1} } });
for (auto cn : adj[node])
{
int child = cn.first, len = cn.second;
if (!is_removed[child] && child != par)
{
map<int, int> prev = dfs_L(child, node);
for (pair<int, int> x : prev)
{
if (cont(lens, x.first + len))
{
auto k = lens[x.first + len];
if (k.second.first > x.second + 1) k.second = { x.second + 1, child };
if (k.first.first > k.second.first) swap(k.first, k.second);
lens[x.first + len] = k;
}
else
{
lens.insert({ x.first + len, { {x.second + 1, child}, {INF, -1} } });
}
}
}
}
printf("Node: %d\n", node);
for (auto& x : lens)
{
printf("%d\t%d\t%d\t%d\t%d\n", x.first, x.second.first.first, x.second.first.second, x.second.second.first, x.second.second.second);
int len = x.first;
auto ko = x.second.first;
if (cont(lens, K - len))
{
auto k = lens[K - len];
if (k.first.second == ko.second)
min_roads = min(min_roads, k.second.first + ko.first);
else min_roads = min(min_roads, k.first.first + ko.first);
}
//if (cont(lens, K - x.first)) min_roads = min(min_roads, x.second + lens[K - x.first]);
//WHAT IF REPEATED PATHS???
}
is_removed[node] = true;
for (auto cn : adj[node])
{
int child = cn.first, len = cn.second;
if (!is_removed[child] && child != par)
min_roads = min(min_roads, compute(child, K, node));
}
return min_roads;
}
int best_path(int N, int K, /*int H[][2]*/int[][2] H, /*int L[]*/ int[] L)
{
adj.assign(N, vector<pair<int,int>>());
subtree_size = v<int>(N, 0);
is_removed.assign(N, false);
for (int i = 0; i < N - 1; i++)
{
adj[H[i][0]].emplace_back(H[i][1], L[i]);
adj[H[i][1]].emplace_back(H[i][0], L[i]);
}
int res = compute(0, K);
if (res == INF) return -1;
else return res;
}