Cerinta completa
HackerLand is a country with beautiful cities and 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 , then the crowd value for the path will be .
Each city has a type value, , denoting the type of buildings in the city.
David just started his vacation in HackerLand. He wants to travel from city to city . He also wants to see at least different types of buildings along the path from to . When choosing a path from city to city that has at least different types of buildings along the path, David always selects the one with the minimum crowd value.
You will be given queries. Each query takes the form of space-separated integers, , , and , 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 and that has at least 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 space-separated integers denoting the respective values for (the number of cities), (the number of roads), and (the number of queries).
The second line contains space-separated integers describing the respective building type for each city in array (where the -th value is and ).
Each of the subsequent lines defines a road in the form of space-separated integers, , , and , defining an undirected road with crowd value that connects cities and .
Each of the subsequent lines defines a query in the form of space-separated integers, , , and (where ), respectively.
Constraints
- Each road connect 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 are shown in different colors.
The path for the last query (1 2 4) will be . David sees his first type of building in cities and , his second type of building in city , his third type of building in city , and his fourth type of building in city . The crowd values for each road traveled on this path are ; the maximum of these values is . Thus, we print 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