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;
vector<int> adj[100001];
int G[100001], H[100001];
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;
for (int y: adj[x]){
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;
adj[X].push_back(Y);
adj[Y].push_back(X);
}
G[0]=0, H[0]=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;
}
}
