# Super Maximum Cost Queries

# Super Maximum Cost Queries

nikhil_gupta3591 + 0 comments For first time, i got hint from categroy, problem was posted for.

Kartik1607 + 0 comments The editorials are bad at its best. It explains the solution and not the path to discovery. Here is my take on the solution.

So, we are given a weighted graph, and we are asked to print the number of paths in the graph having cost C.

*Cost of path*= C which is maximum weight of any edge in the path.Suppose I have a graph with N nodes, then

`Total number of edges = (N*(N-1))/2`

Value of C

**can be too big**so I cannot memoize for*all*values of C. But there are**atmost**`10^5`

different value of C, which**can be memoized**Idea : If I can get a graph whose each edge weight

*X or less than X*, then I can calculate number of edges in graph which is answer of cost X.Ah, hah. I can build a graph step by step considering cost of edges in increasing order. ie . First graph would have all edges with cost <= 1, then the graph would be updated for cost <= 2 and so on.

So,

**Step 1: Sort the input by cost**struct Q { int x; int y; long long cost; }; bool compareByCost(const Q &a, const Q &b) { return a.cost < b.cost; } sort(queries.begin(), queries.end(), compareByCost);

Now, I need to process the input, which is nothing but connecting node x with node y.

**Step 2: Creating the graph**for(auto q: queries) { int c = q.cost; join(q.x, q.y, c); }

Here, the join function

*finds the root of x, and root of y*and makes a union of the different tree.I can

**also update the answer**for cost c as well.// Returns root of node X and performs path compression. int getroot(int x) { if (root[x] == x) return x; root[x] = getroot(root[x]); return root[x]; } void join(int a, int b, long long c) { // Getting root of both a and b tress. int roota = getroot(a); int rootb = getroot(b); if(roota == rootb) return; // No need to do anything. They both belong to same tree already root[rootb] = roota; // Different trees, join them long long totalToRemove = 0; long long n = rcount[roota] ; // Number of nodes in tree A totalToRemove += (n*(n-1))/2; n = rcount[rootb] ; totalToRemove += (n*(n-1))/2; // Number of nodes in tree B rcount[roota] += rcount[rootb]; // Tree A now also contains all nodes of tree B. Update the count n = rcount[roota] ; long long totalToAdd = (n*(n-1))/2; // Number of nodes in updated Tree. costCounts[c] += (totalToAdd - totalToRemove); }

So, now my map contains answer for all the given cost. There are

*Q*queries, and at most*N*costs.*Q x N*will cause a Timeout. I now need to find a way to calculate sum for [L,R] fast.Currently my cost map returns returns cost of X, what if my cost map returned cost for all x <= X. A prefix sum!

**Step 3: Optimize cost counts prefix sum**long long maxC = 0; for(auto it: costCounts) { sum += it.second; costSum[it.first] = sum; maxC = max(maxC, it.first); }

Now, i can easily find out answer by binary searching :)

**Step 4: Spit answers**while(q--) { long long l,r; cin>>l>>r; r = min(r, maxC); long long lA = 0, rA; auto left = costSum.lower_bound(l); if (left != costSum.begin()){ --left; lA = left->second; } auto right = costSum.lower_bound(r); if (right->first > r) --right; rA = right->second; long long ans = rA - lA; cout<<ans<<"\n"; }

Any you get a good green Accepted Solution. :)

tpcemail + 0 comments fist i sort the edges,then i caculate the number of paths whos weight not bigger than a value,and put them into a table. last i look up in the table to get answer.it took me so long bu finally i pass all the case!

#include<iostream> #include<vector> using namespace std; //edge struct Edge { int dot1, dot2, weight; }; //for qsort int compare(const void *a, const void *b) { Edge* e1 = (Edge*)a; Edge* e2 = (Edge*)b; return e1->weight - e2->weight; } //number of paths whos weight is no bigger than weight. struct WeightPaths { long long weight, paths; }; //disjoint set's find int find_root(vector<int> &v, int x) { if (v[x] == x) return x; else { v[x] = find_root(v, v[x]); return v[x]; } } //binary search long long search(vector<WeightPaths> &weightPaths, int n) { int min = 0, max = weightPaths.size() - 1; long long result = 0; while (true) { if (max - min <= 1) break; int mean = (min + max) / 2; if (weightPaths[mean].weight > n) max = mean; else min = mean; } if (weightPaths[max].weight <= n) result = weightPaths[max].paths; else result = weightPaths[min].paths; return result; } int main() { int n, q; cin >> n >> q; Edge * Edges = new Edge[n - 1]; for (int i = 0;i < n - 1;i++) cin >> Edges[i].dot1 >> Edges[i].dot2 >> Edges[i].weight; qsort(Edges, n - 1, sizeof(Edge), compare); //sort vector<WeightPaths> weightPaths; WeightPaths wp; wp.weight = 0; wp.paths = 0; weightPaths.push_back(wp); vector<int> root(n + 1), count(n + 1); //disjoint set for (int i = 1;i < n + 1;i++) { root[i] = i; count[i] = 1; } int k = 0; while (k<n-1) { wp.weight = Edges[k].weight; while (k<n - 1 && Edges[k].weight == wp.weight) { int dot1 = Edges[k].dot1; int dot2 = Edges[k].dot2; int r1, r2; r1 = find_root(root, dot1); r2 = find_root(root, dot2); if (r1 != r2) { wp.paths += (long long)count[r2] * count[r1]; // caculate new paths root[r2] = r1; count[r1] += count[r2]; count[r2] = 0; } k++; } weightPaths.push_back(wp); } while (q--) { int l, r; cin >> l >> r; long long ln, rn, p; ln = search(weightPaths, l - 1); rn = search(weightPaths, r); p = rn - ln; cout << p << endl; } return 0; }

lingbo19_tang + 2 comments I'm confused, for example, query [1,2] of the graph should be {3,4} and {1,4}, not {1,3} because 1 -> 3 has a cost 3, am I missing something?

jabbarthejack + 0 comments aao kabi haveli pey samjatha

LittleFox + 0 comments Path cost is MAX of edges cost on the path and not SUM of edges cost.

darrinbratt123 + 0 comments Awesome thread! Check out this website for your web development needs.

charleswales914 + 0 comments you can refer to this link on maximizing cost queries

ak0368641 + 0 comments certain info for a very long time. Thank you and good luck [Payment Gateway UAE](https://uaewebsitedevelopment.com/payment-gateway-integration-services/ )

ak0368641 + 0 comments It’s the little changes which will make the greatest changes. Data Recovery Dubai

phamhuynhnhi1 + 0 comments

meghanto20 + 0 comments Python3 implementation using disjoint set and binary search(using bisect module)

from bisect import bisect_left,bisect_right parents = {} rep = {} def make_set(n): global parents,rep parents=dict(zip(range(1,n+1),range(1,n+1))) rep=dict(zip(range(1,n+1),({i} for i in range(1,n+1)))) def add_edge(x, y,paths,w): xroot = find(x) yroot = find(y) paths[w]+=len(rep[xroot])*len(rep[yroot]) if xroot == yroot: return else: if len(rep[yroot])<len(rep[xroot]): parents[yroot] = xroot rep[xroot].update(rep[yroot]) del rep[yroot] else: parents[xroot] = yroot rep[yroot].update(rep[xroot]) del rep[xroot] def find(x): if parents[x] != x: parent = find(parents[x]) parents[x] = parent return parents[x] def solve(tree, queries): n = len(tree)+1 tree.sort(key=lambda e:e[2]) paths = {0:0} weights = [0] prev = 0 make_set(len(tree)+1) for a,b,w in tree: if w != prev: weights.append(w) paths[w] = paths[prev] add_edge(a,b,paths,w) prev=w for l,r in queries: wr = weights[bisect_right(weights,r)-1] wl = weights[bisect_right(weights,l-1)-1] yield paths[wr]-paths[wl]

Sort 30 Discussions, By:

Please Login in order to post a comment