Milk Visits Runtime Error

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!


#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) {
    visited[node] = true;
    for (const int& child : graph[node]) dfs(child, breed);

int main() {
  ifstream cin("");
  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;
  for (int i = 1; i <= n; i++) {
    dfs(i, breeds[i]);
  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;
    if (found) cout << 0;
    else cout << 1;
  return 0;

Looks like the bucket count of unordered_set doesn’t decrease when you clear it (so pushing \sim N elements to components could result in \sim N^2 memory?). Replacing component.clear(); with component = unordered_set<int>(); converts it to TLE.

Thank you! Can you give a hint about why it is tle’ing? I am so confused about this problem

takes time proportional to MN