My issue Why is this giving WA?
My approach:
First i am sorting the roads based on their z value(cost)
I am greedily choosing the roads that are either negative or connect a previously unconnected component.
Since i am connecting the components starting from the lowest cost roads and since all Houses must be present in some road connection all houses get connected with lowest cost.
My code
# cook your dish here
void solve(){
ll n,m;cin>>n>>m;
string s;cin>>s;
vector<vector<ll>>a;
for(int i=0;i<m;i++){
ll x,y,z;cin>>x>>y>>z;
x--;y--;
a.pb({z,x,y});
}
ll res=0;
set<ll>mp;
sort(all(a));
for(auto i:a){
//take only if both are houses and one connected other isnt or
//one is house and other is R and the house isn't connected
ll z=i[0],x=i[1],y=i[2];
if(z<0){
res+=z;
mp.insert(x);
mp.insert(y);
continue;
}
else if((s[x]=='H' && s[y]=='H')){
if(mp.count(x) && mp.count(y)){//both are connected houses
continue;
}
else if(mp.count(x) || mp.count(y)){//atleast one connected
res+=z;
mp.insert(x);
mp.insert(y);
}
}
else if(s[x]=='H' && s[y]=='R' && !mp.count(x)){
mp.insert(x);
res+=z;
}
else if(s[x]=='R' && s[y]=='H' && !mp.count(y)){
mp.insert(y);
res+=z;
}
}
cout<<res<<"\n";
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
ll t;
cin>>t;
while(t--) solve();
}
Problem Link: https://www.codechef.com/problems/RHOUSE