oj.uz

Submission #876035

# Submission time Handle Problem Language Result Execution time Memory
876035 2023-11-21T06:33:11 Z Zian_Jacobson Race (IOI11_race) C++17
21 / 100
 3000 ms 25172 KB 
#include "race.h"
#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
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

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2492 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2552 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2492 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2552 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 3 ms 2396 KB Output is correct
22 Correct 5 ms 2652 KB Output is correct
23 Correct 5 ms 2616 KB Output is correct
24 Correct 3 ms 2576 KB Output is correct
25 Correct 3 ms 2652 KB Output is correct
26 Correct 3 ms 2624 KB Output is correct
27 Correct 2 ms 2396 KB Output is correct
28 Correct 3 ms 2652 KB Output is correct
29 Correct 3 ms 2652 KB Output is correct
30 Correct 3 ms 2652 KB Output is correct
31 Correct 4 ms 2652 KB Output is correct
32 Correct 3 ms 2652 KB Output is correct
33 Correct 5 ms 2652 KB Output is correct
34 Correct 11 ms 2648 KB Output is correct
35 Correct 11 ms 2596 KB Output is correct
36 Correct 13 ms 2652 KB Output is correct
37 Correct 13 ms 2652 KB Output is correct
38 Correct 9 ms 2700 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2492 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2552 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 510 ms 12640 KB Output is correct
20 Correct 470 ms 12624 KB Output is correct
21 Correct 420 ms 12788 KB Output is correct
22 Correct 290 ms 12628 KB Output is correct
23 Correct 757 ms 13284 KB Output is correct
24 Correct 200 ms 12632 KB Output is correct
25 Execution timed out 3074 ms 25172 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2492 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2648 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2552 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2396 KB Output is correct
18 Correct 1 ms 2396 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 3 ms 2396 KB Output is correct
22 Correct 5 ms 2652 KB Output is correct
23 Correct 5 ms 2616 KB Output is correct
24 Correct 3 ms 2576 KB Output is correct
25 Correct 3 ms 2652 KB Output is correct
26 Correct 3 ms 2624 KB Output is correct
27 Correct 2 ms 2396 KB Output is correct
28 Correct 3 ms 2652 KB Output is correct
29 Correct 3 ms 2652 KB Output is correct
30 Correct 3 ms 2652 KB Output is correct
31 Correct 4 ms 2652 KB Output is correct
32 Correct 3 ms 2652 KB Output is correct
33 Correct 5 ms 2652 KB Output is correct
34 Correct 11 ms 2648 KB Output is correct
35 Correct 11 ms 2596 KB Output is correct
36 Correct 13 ms 2652 KB Output is correct
37 Correct 13 ms 2652 KB Output is correct
38 Correct 9 ms 2700 KB Output is correct
39 Correct 510 ms 12640 KB Output is correct
40 Correct 470 ms 12624 KB Output is correct
41 Correct 420 ms 12788 KB Output is correct
42 Correct 290 ms 12628 KB Output is correct
43 Correct 757 ms 13284 KB Output is correct
44 Correct 200 ms 12632 KB Output is correct
45 Execution timed out 3074 ms 25172 KB Time limit exceeded
46 Halted 0 ms 0 KB -