Submission #876032

#	Time	Username	Problem	Language	Result	Execution time	Memory
876032		Zian_Jacobson	Race (IOI11_race)	C++17	0 / 100	1 ms	2396 KiB

race

#include<bits/stdc++.h>
#include "race.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


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 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;
}

Compilation message (stderr)

race.cpp: In function 'int compute(int, int, int)':
race.cpp:129:25: warning: unused variable 'len' [-Wunused-variable]
  129 |   int child = cn.first, len = cn.second;
      |                         ^~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57