Hi!
I am quite new on this site, and I am trying to solve some practice problems.
Right now I am trying to tackle Home Delivery problem. I understand that my idea for solution might be unorthodox (silly? unwise… or simply stupid), anyway I can’t grasp why it returns “Wrong Answer”, I even can’t figure out any input for which my approach fails. I guess it’s might be something quite simple, but personally I ran out of ideas (at least for now).
My idea was to keep two arrays: one keeping ‘isolated’ network numbers, and second array with pointers to a proper network number for each location (null pointer means no fast road connection at all). This way I can simply unite two networks by copying the network number to a proper place in a network array if a road connecting two networks is detected.
Any help will be much appreciated!
Here is my code (c++):
using namespace std;
int main() {
// fast I/O mode
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tests; // number of tests
cin >> tests;
for (int i = 0; i < tests; ++i)
{
int n, m, q;
cin >> n; // number of locations
cin >> m; // number of fast roads
const int maxNumberOfLocations = 101;
array<int, maxNumberOfLocations> networkNumbers = {0}; // 0 means not connected to any network
array<int*, maxNumberOfLocations> locations = {nullptr};
int networkCounter = 1;
for (int i = 0; i < m; ++i) // loop over m pairs of fast roads
{
int city1, city2;
cin >> city1 >> city2;
if ( locations[city1] == nullptr)
if ( locations[city2] == nullptr) // when both locations are not present in any network
{
networkNumbers[networkCounter] = networkCounter; // create new network
locations[city1] = &(networkNumbers[networkCounter]); // set pointers to network numbers
locations[city2] = &(networkNumbers[networkCounter]);
networkCounter++; // set up new network number for the next network
}
else // one location is present
{
networkNumbers[city1] = networkNumbers[city2];
locations[city1] = locations[city2];
}
else
if ( locations[city2] == nullptr) // one location is present
{
networkNumbers[city2] = networkNumbers[city1];
locations[city2] = locations[city1];
}
else // both location are present
{
*locations[city2] = *locations[city1]; // connecting two networks
}
}
cin >> q; // number of queries
for (int i = 0; i < q; ++i)
{
int location1, location2;
cin >> location1 >> location2;
if ( locations[location1] != nullptr and locations[location2] != nullptr) // check if both location have roads
{
if (*locations[location1] == *locations[location2]) // check networks numbers
cout << "YO" << endl;
else
cout << "NO" << endl;
}
else
cout << "NO" << endl;
}
}
return 0;
}