Cerinta completa
During the Steam Summer Sale, Jim’s friends have purchased games, which are numbered from to . The games are multiplayer. Jim has invited his friends to his basement where they will play by making a LAN-Party.
Each friend has already decided the game he would like to play for the rest of the day. So there will be a group of friends who will play the same game together.
But then, they face a problem: Currently, none of the friends’ PCs are connected. So they have to be connected using the available wires. Jim decides to connect friends and with the th wire one by one. So he starts with wire 1, then with wire 2 and so on.
A group can start playing their game, only if all the members are connected (if not directly, then there must exist a path connecting them). They want to start playing as soon as possible.
For each game, find out the wire after adding which the group can start playing. It is also possible that a group will never get connected. In such a case, this group starts crying and you should display -1.
Input Format
On the first line there will be , and each separated by a single space. On the second line we will give you integers separated by a single space: The -th integer denotes the game friend wants to play (all between and ). The next lines will denote wires: ith line denotes ith wire and is denoted by and pairs each separated by a single space.
Constraints
For each game , the number of players playing will be positive.
Note
Each game is chosen by at least one player. If a group consists of only one member, then print 0, since this lucky (?) lone player can start right away!
Output Format
Print on the th line the answer for the th game.
Sample Input
5 2 4
1 2 2 2 1
1 2
2 3
1 5
4 5
Sample Output
3
4
Explanation
The group with the game 1 can play after the 3rd wire is added. The group with game 2 can play only after the 4th wire has been added because after adding the 4th wire, a path between (2,3) (3,4) and (2,4) gets created.
Limbajul de programare folosit: cpp14
Cod:
#include <bits/stdc++.h>
using namespace std;
vector<string> split_string(string);
namespace waldek
{
template<class T=size_t>
class DisjointSet
{
public:
typedef T type;
///@returns number of independent sets/*
type size()const { return m_size; }
///@returns size of set contains 'x'
type size(type x) { return m_arr[find(x)].size; }
///@returns size of bigest set
type getMax()const{ return m_max; }
///@returns set where x belong to
size_t find(type x)
{
auto res = m_arr.find(x);
if(res==m_arr.end())
{
m_arr[x] = {x,1};
m_size++;
m_max = std::max(m_max, type(1) );
}
auto root = x;
while( m_arr[root].parent != root )
root = m_arr[root].parent;
while( m_arr[x].parent != root )
{
auto parent = m_arr[x].parent;
m_arr[x].parent = root;
x = parent;
}
return root;
}
///@returns merged set
type merge(type a, type b)
{
type aa = find(a);
type bb = find(b);
if(aa==bb)
return aa;
else if(aa<bb)
{
m_arr[bb].parent = aa;
m_arr[aa].size += m_arr[bb].size;
m_size--;
m_max = std::max(m_max, m_arr[aa].size);
return aa;
}
else
{
m_arr[aa].parent = bb;
m_arr[bb].size += m_arr[aa].size;
m_size--;
m_max = std::max(m_max, m_arr[bb].size);
return bb;
}
}
private:
struct Set
{
type parent;
type size;
};
std::unordered_map<type,Set> m_arr;
type m_size=0;
type m_max=0;
};
}
int checkNetwork(waldek::DisjointSet<>& ds, vector<int>& checkpoints, int start)
{
cout<<" check:"<<checkpoints[start];
for(int i=start; i<(int)checkpoints.size(); i++)
{
cout<<","<<checkpoints[i];
if( ds.find(checkpoints[0])!=ds.find(checkpoints[i]) )
{ cout<<" -> "<<checkpoints[i]<<":"<<i<<endl;
return i;
}
}
cout<<" -> -1"<<endl;
return -1;
}
vector<int> lanParty(//-------------------------------------------------------------
const vector<int>& games,
const vector<vector<int>>& wires,
int m
)
{
vector<int> ret(m,0);
vector<vector<int>> g2f(m+1);
for(int i=0; i<(int)games.size() ; i++)
g2f[games[i]].push_back(i+1);
waldek::DisjointSet<> network;
int cable =0;
int res =0;
for(int game=1 ; game<=m ; ++game)
{
if(g2f[game].size()==1)
{
ret[game-1]=0;
continue;
}
if(wires.size()==0 && g2f[game].size()>1)
{
ret[game-1]=-1;
continue;
}
res =0;
cout<<"game:"<<game<<endl;
while(cable<(int)wires.size() && res!=-1)
{
ret[game-1]=cable+1;
cout<<" add: "<<cable+1
<<" "<<wires[cable][0]
<<","<<wires[cable][1]
<<" ,res:"<<ret[game-1]<<endl;
network.merge(wires[cable][0], wires[cable][1]);
res= checkNetwork(network, g2f[game], res);
cable++;
}
if(cable>=(int)wires.size() && res>0) ret[game-1]=-1;
else if(
cable>=(int)wires.size() &&
game>1 &&
(ret[game-1]<ret[game-2] || ret[game-2]==-1)
){
int r =checkNetwork(network,g2f[game],0);
ret[game-1]= r!=-1 ? -1 : cable;
}
}
return ret;
}
int main()
{
ofstream fout(getenv("OUTPUT_PATH"));
string nmq_temp;
getline(cin, nmq_temp);
vector<string> nmq = split_string(nmq_temp);
int n = stoi(nmq[0]);
int m = stoi(nmq[1]);
int q = stoi(nmq[2]);
string games_temp_temp;
getline(cin, games_temp_temp);
vector<string> games_temp = split_string(games_temp_temp);
vector<int> games(n);
for (int games_itr = 0; games_itr < n; games_itr++) {
int games_item = stoi(games_temp[games_itr]);
games[games_itr] = games_item;
}
vector<vector<int>> wires(q);
for (int wires_row_itr = 0; wires_row_itr < q; wires_row_itr++) {
wires[wires_row_itr].resize(2);
for (int wires_column_itr = 0; wires_column_itr < 2; wires_column_itr++) {
cin >> wires[wires_row_itr][wires_column_itr];
}
cin.ignore(numeric_limits<streamsize>::max(), '\n');
}
vector<int> result = lanParty(games, wires, m);
for (int result_itr = 0; result_itr < (int)result.size(); result_itr++) {
fout << result[result_itr];
if (result_itr != (int)result.size() - 1) {
fout << "\n";
}
}
fout << "\n";
fout.close();
return 0;
}
vector<string> split_string(string input_string) {
string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
return x == y and x == ' ';
});
input_string.erase(new_end, input_string.end());
while (input_string[input_string.length() - 1] == ' ') {
input_string.pop_back();
}
vector<string> splits;
char delimiter = ' ';
size_t i = 0;
size_t pos = input_string.find(delimiter);
while (pos != string::npos) {
splits.push_back(input_string.substr(i, pos - i));
i = pos + 1;
pos = input_string.find(delimiter, i);
}
splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));
return splits;
}
Scor obtinut: 1.0
Submission ID: 464650129
Link challenge: https://www.hackerrank.com/challenges/jim-and-his-lan-party/problem