Soluție HackerRank pentru Travel in HackerLand. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Travel in HackerLand

Cerinta completa

HackerLand is a country with [Expresie matematică indisponibilă în copia arhivată] beautiful cities and [Expresie matematică indisponibilă în copia arhivată] undirected roads. Like every other beautiful country, HackerLand has traffic jams.

Each road has a crowd value. The crowd value of a path is defined as the maximum crowd value for all roads in the path. For example, if the crowd values for all roads are [Expresie matematică indisponibilă în copia arhivată], then the crowd value for the path will be [Expresie matematică indisponibilă în copia arhivată].

Each city [Expresie matematică indisponibilă în copia arhivată] has a type value, [Expresie matematică indisponibilă în copia arhivată], denoting the type of buildings in the city.

David just started his vacation in HackerLand. He wants to travel from city [Expresie matematică indisponibilă în copia arhivată] to city [Expresie matematică indisponibilă în copia arhivată]. He also wants to see at least [Expresie matematică indisponibilă în copia arhivată] different types of buildings along the path from [Expresie matematică indisponibilă în copia arhivată] to [Expresie matematică indisponibilă în copia arhivată]. When choosing a path from city [Expresie matematică indisponibilă în copia arhivată] to city [Expresie matematică indisponibilă în copia arhivată] that has at least [Expresie matematică indisponibilă în copia arhivată] different types of buildings along the path, David always selects the one with the minimum crowd value.

You will be given [Expresie matematică indisponibilă în copia arhivată] queries. Each query takes the form of [Expresie matematică indisponibilă în copia arhivată] space-separated integers, [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată], denoting the respective values for starting city, destination city, and minimum number of unique buildings that David wants to see along the way. For each query, you must print the minimum crowd value for a path between [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată] that has at least [Expresie matematică indisponibilă în copia arhivată] different buildings along the route. If there is no such path, print -1.

Note: A path may contain cycles (i.e., the same roads or cities may be traveled more than once).

Input Format

The first line contains [Expresie matematică indisponibilă în copia arhivată] space-separated integers denoting the respective values for [Expresie matematică indisponibilă în copia arhivată] (the number of cities), [Expresie matematică indisponibilă în copia arhivată] (the number of roads), and [Expresie matematică indisponibilă în copia arhivată] (the number of queries).

The second line contains [Expresie matematică indisponibilă în copia arhivată] space-separated integers describing the respective building type for each city in array [Expresie matematică indisponibilă în copia arhivată] (where the [Expresie matematică indisponibilă în copia arhivată]-th value is [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată]).

Each of the [Expresie matematică indisponibilă în copia arhivată] subsequent lines defines a road in the form of [Expresie matematică indisponibilă în copia arhivată] space-separated integers, [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată], defining an undirected road with crowd value [Expresie matematică indisponibilă în copia arhivată] that connects cities [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată].

Each of the [Expresie matematică indisponibilă în copia arhivată] subsequent lines defines a query in the form of [Expresie matematică indisponibilă în copia arhivată] space-separated integers, [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată] (where [Expresie matematică indisponibilă în copia arhivată]), respectively.

Constraints

  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]
  • Each road connect [Expresie matematică indisponibilă în copia arhivată] distinct cities, meaning no road starts and ends in the same city.

Output Format

For each query, print its answer on a new line.

Sample Input

7 6 1
1 1 4 5 1 3 2
1 2 3
2 6 2
2 3 4
3 4 3
2 4 9
5 7 9
1 2 4

Sample Output

4

Explanation

The diagram below depicts the country given as Sample Input. Different values of [Expresie matematică indisponibilă în copia arhivată] are shown in different colors.

Rețea cu șapte orașe, tipurile de clădiri marcate prin culori și drumurile etichetate cu valorile 2, 3, 4 și 9.

The path for the last query (1 2 4) will be [Expresie matematică indisponibilă în copia arhivată]. David sees his first type of building in cities [Expresie matematică indisponibilă în copia arhivată] and [Expresie matematică indisponibilă în copia arhivată], his second type of building in city [Expresie matematică indisponibilă în copia arhivată], his third type of building in city [Expresie matematică indisponibilă în copia arhivată], and his fourth type of building in city [Expresie matematică indisponibilă în copia arhivată]. The crowd values for each road traveled on this path are [Expresie matematică indisponibilă în copia arhivată]; the maximum of these values is [Expresie matematică indisponibilă în copia arhivată]. Thus, we print [Expresie matematică indisponibilă în copia arhivată] on a new line.

Limbajul de programare folosit: cpp14

Cod:

#include <ios>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <algorithm>

struct st
{
	std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > pq;
	//priority queue contains (DISTINCT CITIES REQUIRED, query#) sorted by smallest cities required first
	std::map<int, int> c; //(query#, cities found) when it becomes 2, we add it to the pq
	std::set<int> ds; //distinct types
};

int par[100005] = {};
int siz[100005] = {};
int req[100005] = {};
int ans[100005] = {}; //store the answers here
std::vector<std::pair<int, std::pair<int, int> > > quers; // weight, a, b
std::vector<st> vec;

void merge_and_check(int a, int b, int w) //merge b to a
{
	for (std::set<int>::iterator it = vec[b].ds.begin(); it != vec[b].ds.end(); it++)
		vec[a].ds.insert(*it);
	while (!vec[b].pq.empty())
	{
		vec[a].pq.push(vec[b].pq.top());
		vec[b].pq.pop();
	}
	for (std::map<int, int>::iterator it = vec[b].c.begin(); it != vec[b].c.end(); it++)
	{
		if (vec[a].c.find(it->first) == vec[a].c.end())
			vec[a].c.insert(std::make_pair(it->first, it->second));
		else
		{
			vec[a].c[it->first]++;
			if (vec[a].c[it->first] == 2)
				vec[a].pq.push(std::make_pair(req[it->first], it->first));
		}
	}
			
	vec[b].ds.clear();
	vec[b].c.clear();
			
	while (!vec[a].pq.empty() && vec[a].pq.top().first <= vec[a].ds.size())
	{
		ans[vec[a].pq.top().second] = w;
		vec[a].pq.pop();
	}
}

int fnd(int a)
{
	int x = par[a];
	while (x != par[x])
		x = par[x];
	return x;
}

void join(int a, int b, int w)
{
	a = fnd(a);
	b = fnd(b);
	if (a != b)
	{
		//time to merge
		if (siz[a] > siz[b])
		{
			siz[a] += siz[b];
			par[b] = a;
			merge_and_check(a, b, w);
		}
		else if (siz[a] < siz[b])
		{
			siz[b] += siz[a];
			par[a] = b;
			merge_and_check(b, a, w);
		}
		else
		{
			siz[a] += siz[b];
			par[b] = a;
			merge_and_check(a, b, w);
		}
	}
}

int main()
{
	for (int i = 0; i < 100005; i++)
	{
		par[i] = i;
		siz[i] = 1;
		ans[i] = -1;
	}
		
	int n, m, q, a, b, w, x, y;
	std::cin >> n >> m >> q;
	for (int i = 0; i < n; i++)
		vec.push_back(st());
	for (int i = 0; i < n; i++)
	{
		std::cin >> x;
		vec[i].ds.insert(x);
	}
	for (int i = 0; i < m; i++)
	{
		std::cin >> a >> b >> w;
		a--; b--;
		quers.push_back(std::make_pair(w, std::make_pair(a, b)));
	}
	for (int i = 0; i < q; i++)
	{
		std::cin >> x >> y >> req[i];
        x--; y--;
		if (x == y)
		{
			if (req[i] == 1)
				ans[i] = 0;
            else
			{
				vec[x].c.insert(std::make_pair(i, 2));
				vec[x].pq.push(std::make_pair(req[i], i));
			}
		}
		else
		{
			vec[x].c.insert(std::make_pair(i, 1));
			vec[y].c.insert(std::make_pair(i, 1));
		}
	}
	std::sort(quers.begin(), quers.end());
	for (std::vector<std::pair<int, std::pair<int, int> > >::iterator it = quers.begin(); it != quers.end(); it++)
	{
		join(it->second.first, it->second.second, it->first);
	}
	for (int i = 0; i < q; i++)
		std::cout << ans[i] << '\n';
}

Scor obtinut: 1.0

Submission ID: 464650135

Link challenge: https://www.hackerrank.com/challenges/travel-in-hackerland/problem

Travel in HackerLand