Undirected graph with weights

closed account (1vf9z8AR)
Question-
https://www.hackerearth.com/practice/data-structures/trees/binary-search-tree/practice-problems/algorithm/mst-revisited-3f9d614c/description/

Issue-
I am not able to understand why my answer is wrong. It passes sample test cases.
Is there something wrong with the insertion and deletion of edge?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
  #include<iostream>
#include<vector>
#include<utility>
#include<map>
using namespace std;
void cmp(int &u,int &v)  //to find smaller number
{
    if(v<u)
    {
        int t=v;
        v=u;
        u=t;
    }
}
int main()
{
    int n,q;
    cin>>n>>q;
    map<int,vector<pair<int,int>>>m; //first,second,weight
    pair<int,int>p;
    int u,v,c;
    long long int weight=0;
    for(int i=0;i<n;i++)
    {
        cin>>u>>v>>c; //first,second,weight
        cmp(u,v);
        weight+=c; //add to weight
        p=make_pair(v,c);
        m[u].push_back(p); //create edge
    }
    long long int ans=0;
    int x1,x2,x3,x4,x5,a,b;
    for(int i=0;i<q;i++)
    {
        cin>>x1>>x2>>x3>>x4>>x5;  //enter the five numbers
        ans=ans%100;
        a=x1+ans;   //first no of edge to delete
        b=x2+ans;   //second no of edge to delete
        u=x3+ans;   //first no of edge to add
        v=x4+ans;   //second no of edge to add
        c=x5+ans;   //weight of edge to add
        cmp(u,v); 
        cmp(a,b);
        for(vector<pair<int,int>>::iterator it=m[a].begin();it!=m[a].end();it++)
        {
            if(it->first==b) //found edge
            {
                weight-=it->second; //decrease net weight
                m[a].erase(it); //delete edge
                break;
            }
        }
        ans=weight; 
        cout<<ans<<endl;    //output answer
        p=make_pair(v,c);   
        m[u].push_back(p); //add edge
        weight+=c;          //add to net weight
    }
}
Last edited on
Topic archived. No new replies allowed.