0 like 0 dislike
1,164 views
| 1,164 views

0 like 0 dislike

images of ques

by Expert (46,090 points)
0 like 0 dislike

C++ solution with comments both test cases passed
Simple dfs solution keeping the count of number of cars and number of people and merging max possible number of people (5) in same car.
Let me if anyone has a test case that gives WA.

``````// snippet by shubham7811
#include<bits/stdc++.h>
using namespace std;

pair<int, int> dfs(int curr, vector<vector<int>> &g, vector<int> &vis, int &ans) {
vis[curr] = 1;
int people = 1;
for (int x : g[curr]) {
if (vis[x]) continue;
pair<int, int> res = dfs(x, g, vis, ans);
// adding number of people to combine them in same cars
people += res.first;
// adding number of cars that came to this point as each car will take 1ltr fuel
ans += res.second;
}
int cars = (people + 4) / 5;  // number of 5 seater cars required
return {people, cars};
}

int solution(vector<int> &A, vector<int> &B) {
int n = A.size() + 1; // number of nodes
vector<vector<int>> g(n);
for (int i = 0; i < n - 1; i++) {
int a = A[i];
int b = B[i];
g[a].push_back(b);
g[b].push_back(a);
}
vector<int> vis(n);
int ans = 0; // ans -> will pass in dfs function by reference
dfs(0, g, vis, ans);
return ans;
}

int32_t main() {
int t = 1;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> A(n), B(n);
for (int i = 0; i < n; i++)
cin >> A[i];
for (int i = 0; i < n; i++)
cin >> B[i];
cout << solution(A, B) << endl;
}
return 0;
}

/*
INPUT
2
3
0 1 1
1 2 3
9
1 1 1 9 9 9 9 7 8
2 0 3 1 6 5 4 0 0

*/``````
by Expert (46,090 points)
0 like 0 dislike

Suppose the graph(tree) as rooted in node 0. We make a dfs on node 0 and dfs call on a node return two things, 1)number of nodes under its subtree(including itself) and 2)minimum fuel spent for all people under its subtree to come to this node.

``````import math

def solution(A, B):
n = len(A)
adj = [[] for _ in range(n + 1)]
for u, v in zip(A, B):

visited = set()

def dfs(node):

subtree_nodes_count = 1
subtree_fuel_spent = 0
if neighbor not in visited:
nodes_count, fuel_spent = dfs(neighbor)
subtree_nodes_count += nodes_count
subtree_fuel_spent += (fuel_spent + math.ceil(nodes_count / 5))

return subtree_nodes_count, subtree_fuel_spent

return dfs(0)[1]

print(
solution(
[1, 1, 1, 9, 9, 9, 9, 7, 8],
[2, 0, 3, 1, 6, 5, 4, 0, 0]
)
)``````
by Expert (46,090 points)
0 like 0 dislike

Simple DFS solution.

``````int ans;
public int minFuel(int[] a, int[] b, int n) {
List<Integer>[] outs = new List[n+1];
for(int i=0; i<a.length; i++) {
if(outs[a[i]]==null) outs[a[i]] = new ArrayList<>();
if(outs[b[i]]==null) outs[b[i]] = new ArrayList<>();
}
ans = 0;
boolean[] visited = new boolean[n+1];
dfs(0, outs, visited);
return ans;
}

private int dfs(int node, List<Integer>[] outs, boolean[] visited) {
visited[node] = true;
int passengers = 0;
for(int neighbor : outs[node]) {
if(visited[neighbor]) continue;
passengers+=dfs(neighbor, outs, visited);
}
passengers++;
if(node!=0) ans+=(passengers-1)/5+1;
return passengers;
}``````
by Expert (46,090 points)