# Help me for Milk Visits (code gets half the test cases right)

Hi, I need help debugging Milk Visits (USACO Silver 2019/Dec/3). Basically, what happens is my code works for around half the test cases, but gets the wrong answer for the other half.

My solution was a bit different from the official solution. Instead of doing connected components, I used prefix sums on the tree. I rooted the tree at node 1, and then for each node I stored in an array how many G’s and how many H’s you encounter on the path from 1 to that node. Then, for each path given in the input, I used that to find how many G’s or H’s are along that path. I then printed the answer based on whether this quantity was 0 or not 0.

Could someone please help me figure out where I went wrong? This is especially baffling to me because around half the test cases do work.

## My Code

``````#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <numeric>
using namespace std;
using ll=long long;
using ull=unsigned long long;

int G, H;
string s;

void dfs(int x, int p){
if (s[x]=='G') G[x]=G[p]+1, H[x]=H[p];
if (s[x]=='H') G[x]=G[p], H[x]=H[p]+1;
if (y!=p) dfs(y, x);
}
return;
}

int main() {
ifstream cin("milkvisits.in");
int N, M;
cin>>N>>M;
cin>>s;
s="."+s;
// cout<<s;
for (int i=1; i<N; i++){
int X, Y;
cin>>X>>Y;
}
G=0, H=0;
dfs(1, 0);
ofstream fout("milkvisits.out");
for (int z=0; z<M; z++){
int A, B;
char C;
cin>>A>>B>>C;
int t;
if (C=='G') t=abs(G[A]-G[B])+(int)(s[B]=='G');
if (C=='H') t=abs(H[A]-H[B])+(int)(s[B]=='H');
if (t>0) fout<<1;
else fout<<0;
}
}
``````

I’m pretty sure what goes wrong in your algorithm is that it cannot tell the difference between these two scenarios as demonstrated by this, albeit poor, drawing. With 4 and 6 being the queried route for a Holstein farmer.

Your algorithm always assumes Scenario B which causes it to get queries incorrect. Hopefully this clears things up, and if it doesn’t, I would be happy to answer any questions.

2 Likes

Oh I see, that makes sense. I totally missed that. Thanks for catching my mistake!