We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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>usingnamespacestd;//edgestructEdge{intdot1,dot2,weight;};//for qsort intcompare(constvoid*a,constvoid*b){Edge*e1=(Edge*)a;Edge*e2=(Edge*)b;returne1->weight-e2->weight;}//number of paths whos weight is no bigger than weight.structWeightPaths{longlongweight,paths;};//disjoint set's find intfind_root(vector<int>&v,intx){if(v[x]==x)returnx;else{v[x]=find_root(v,v[x]);returnv[x];}}//binary searchlonglongsearch(vector<WeightPaths>&weightPaths,intn){intmin=0,max=weightPaths.size()-1;longlongresult=0;while(true){if(max-min<=1)break;intmean=(min+max)/2;if(weightPaths[mean].weight>n)max=mean;elsemin=mean;}if(weightPaths[max].weight<=n)result=weightPaths[max].paths;elseresult=weightPaths[min].paths;returnresult;}intmain(){intn,q;cin>>n>>q;Edge*Edges=newEdge[n-1];for(inti=0;i<n-1;i++)cin>>Edges[i].dot1>>Edges[i].dot2>>Edges[i].weight;qsort(Edges,n-1,sizeof(Edge),compare);//sortvector<WeightPaths>weightPaths;WeightPathswp;wp.weight=0;wp.paths=0;weightPaths.push_back(wp);vector<int>root(n+1),count(n+1);//disjoint setfor(inti=1;i<n+1;i++){root[i]=i;count[i]=1;}intk=0;while(k<n-1){wp.weight=Edges[k].weight;while(k<n-1&&Edges[k].weight==wp.weight){intdot1=Edges[k].dot1;intdot2=Edges[k].dot2;intr1,r2;r1=find_root(root,dot1);r2=find_root(root,dot2);if(r1!=r2){wp.paths+=(longlong)count[r2]*count[r1];// caculate new pathsroot[r2]=r1;count[r1]+=count[r2];count[r2]=0;}k++;}weightPaths.push_back(wp);}while(q--){intl,r;cin>>l>>r;longlongln,rn,p;ln=search(weightPaths,l-1);rn=search(weightPaths,r);p=rn-ln;cout<<p<<endl;}return0;}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Super Maximum Cost Queries
You are viewing a single comment's thread. Return to all 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!