No, we can’t answer, whether there’s an edge from A to B in O(1), we have to traverse the list which take O(Listsize). But, in DFS, we don’t need to know this, so the adjacency list is better.
Yes got that now, cant thank you enough !!!
1 Like
Can someone please tell me, where am I getting wrong? I have used a bfs approach, finding the cost to reach all the leaf nodes, then, calculating the answer with simple two-pointers method.
Here is the submission link: CodeChef: Practical coding for everyone. I have also attached the code below.
int n, m;
cin >> n >> m;
vector<int> eng(m);
for (int i=0; i<m; i++) cin >> eng[i];
vector<vector<pair<int,int>>> adj(n+1);
for (int i=1; i<=n-1; i++) {
int x, y, z;
cin >> x >> y >> z;
adj[x].pb({y,z});
}
vector<int> level(n+1);
queue<pair<int,int>> q;
q.push({1,1});
level[1] = 1;
while (!q.empty()) {
auto top = q.front();
q.pop();
for (auto a: adj[top.first]) {
level[a.first] = top.second+1;
q.push({a.first, level[a.first]});
}
}
vector<int> cost(n+1, 0);
queue<int> q1;
q1.push(1);
while (!q1.empty()) {
int top = q1.front();
q1.pop();
for (auto a: adj[top]) {
cost[a.first] = a.second * level[top] + cost[top];
q1.push({a.first});
}
}
vector<int> target;
for (int i=1; i<adj.size(); i++) {
if (adj[i].size() == 0) {
target.pb(cost[i]);
}
}
sort(all(target));
sort(all(eng));
int res = 0, i = 0, j = 0;
while (i < eng.size() && j < target.size()) {
if (eng[i] >= target[j]) {
i++;
j++;
res++;
} else i++;
}
cout << res << "\n";
1 Like
You have to input the edges in a bidirectional way and not in a unidirectional way.
Add this - adj[y].pb({x,z});
I think your way of calculating the reduction of energy is wrong. Run a DFS and calculate the reduction of energy.
Anyways, Can you explain your approach?
Is it necessary to use dfs because I code without use of dfs by apply simple math and calculation .
can u give me some test case because the given test case in Q in passed is cleared by my code but i didnot know why it showing WA
1 Like
Are you considering all the leaf nodes(except node 1)?
1 Like
i did not make a single node in my code did this Q by simple mathematics
1 Like
I didn’t literally mean node. I meant that have you considered 1st city as the special city?
It seems my code is correct for problem D- CodeChef: Practical coding for everyone
But I am getting WA in it, I have also covered the corner case (didn’t consider 1 as the special city).
Can anyone point out the mistake, where I am going wrong
I did it using simple maths?
Can some help me in my submission for this problem . I am not able to find the bug in my code . I used BFS for this problem . The problem link is my_solution . Thanks in advance .
Can suggest where the SIGSEGV occurring. I don’t find where does this happen: CodeChef: Practical coding for everyone