Hi, I was recently doing the silver problem Milk Visits, Link to Problem. My solution logic is similar to the official solution, where I divided Farmer John’s farms into connected components based on the cow breed in that farm. My code is working fine for the first 5 testcases, but gets runtime error for the rest of the testcases. I can’t find any part of my code that might produce a runtime error, so therefore I suspect it might have something to do with memory. Any help will be appreciated, thank you!
Code:
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <fstream>
#include <list>
#include <unordered_set>
using namespace std;
int n, m;
list<int> graph[100001];
char breeds[100001];
int visited[100001];
vector<unordered_set<int>> components;
unordered_set<int> component;
void dfs(int node, int breed) {
if (!visited[node] && breeds[node] == breed) {
component.insert(node);
visited[node] = true;
for (const int& child : graph[node]) dfs(child, breed);
}
}
int main() {
ifstream cin("milkvisits.in");
ofstream cout("milkvisits.out");
cin >> n >> m;
for (int i = 1; i <= n; i++) {
char a;
cin >> a;
breeds[i] = a;
}
for (int i = 0; i < n-1; i++) {
int a, b;
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
dfs(i, breeds[i]);
components.push_back(component);
component.clear();
}
for (int i = 0; i < m; i++) {
int a, b;
char c;
cin >> a >> b >> c;
if (c == 'G') c = 'H';
else if (c == 'H') c = 'G';
bool found = false;
for (const unordered_set<int>& component : components) {
if (component.find(a) != component.end() && component.find(b) != component.end()) {
if (breeds[a] == c) {
found = true;
break;
}
}
}
if (found) cout << 0;
else cout << 1;
}
return 0;
}