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.
  1. All Contests
  2. HourRank 22
  3. Super Mancunian
  4. Discussions

Super Mancunian

Sort by

recency

|

20 Discussions

|

  • enricogiurin
     + 0 comments

    Finally I solved it. It took a few days to understand that several tests failed for timeout because I was using a slow implementation of UnionFind O(N). As soon as I switched to QuickUnionUF O(logN) all the tests became green.

    http://vancexu.github.io/2015/07/13/intro-to-union-find-data-structure.html

  • thedsk8
     + 0 comments

    I am getting segmentation fault in all the test cases except one.Is it because my solution uses too much space or there is any other mistake in it.

    #include<bits/stdc++.h>
using namespace std;
int main()
{
long long int n,m,x,y,max1,min1,cost=0,cm=0,cn;
cin>>n>>m;
vector<long long int> a[n+1];
long long int i,c[n+1][n+1];
for(i=0;i<m;i++)
{
    cin>>x>>y;
    if(x!=y)
    a[x].push_back(y);
    if(x!=y)
    a[y].push_back(x);
    cin>>c[x][y];
    c[y][x]=c[x][y];
    //sf[c[x][y]]++;
}
for(i=2;i<=n;i++)
{
    for(unsigned long long int j=0;j<a[i].size();j++)
    {
        if(j==0)
        {
            min1=c[a[i][j]][i];
           /* if(i==0)
                max1=min1;*/
        }
        /*if(max1==c[a[i][j]][i])
            cm++;*/
        else
        {
            if(min1>c[a[i][j]][i])
                min1=c[a[i][j]][i];
        }

    }
    //cout<<min1;
    if(i==2)
        max1=min1;
    cost+=min1;
    if(max1<min1)
    {
        max1=min1;
    }
        //cout<<max1;
}

    for(i=1;i<=n;i++)
    {

        for(unsigned long long int k=0;k<a[i].size();k++)
        {
            //cout<<c[a[i][k]][i]<<endl;
            if(c[a[i][k]][i]==max1)
                cm++;
        }
    }
cout<<cost-max1<<" "<<cm/2;
return 0;
}

  • GWeasel
     + 2 comments

    Is this test case giving the correct answer?

    5 5 1 2 1 2 3 2 2 4 2 3 4 2 5 3 3

    Shouldn't the output be 5 3 instead of 5 1

  • Anonymous_1998
     + 0 comments

    Hey guys I'm getting only 24.38 points. Here is a psuedo code of mine.

    lli Kruskal()
{
	lli Minimum_Cost=0;
	lli i;
	
	rep(i,0,V.sz())
	{
		lli x=V[i].S.F;
		lli y=V[i].S.S;
		lli w=V[i].F;
		
		if(root(x)!=root(y))
		{
		    cnt++;
		    
		    if(cnt==N-1)
		    {
		        cnt--;
		        Count++;
		    }
		    else
            {
                Union(x,y);
			
		     	Minimum_Cost+=w;
            }
        }
	}
	
 return Minimum_Cost;	
}

    And I print Minimum_Cost and Count.

  • local_bantai
     + 1 comment

    In case the problem was more generalized, say that the level we start from will also be given as input (and not LEVEL 1 by default as in this problem), would we get the solution by using All-Pairs-Shortest-Path and our answer would be count of all the edges having weight equal to the maximum weight in the graph?