You are not logged in. Please login at www.codechef.com to post your questions!

×

galactik.. giving WA. plz help

#include <cstdio>
#include<algorithm>
#include <cstring>
#include <vector>
using namespace std;

const int maxN = 100010;
vector<int> a[maxN];
vector<int> x;
int mark[maxN];
int value[maxN];
int mini=10000000;

void dfs(int u)
{
    mark[u]=1;
    if(value[u] < mini && value[u]>=0)
    mini= value[u];

    for(int i=a[u].size();i--;)
    {
        int v=a[u][i];
        if(!mark[v]) dfs(v);
    }
}

int main()
{
        int n,m,flag=0,minx=0;
        scanf("%d%d",&n,&m);

        int i,u,v;
        long long sum=0;
        for(i=0;i<n;i++) {
            a[i].clear();
            mark[i]=0;
        }
        for(int k=0;k<m;k++)
        {
            scanf("%d%d",&u,&v);
            a[u-1].push_back(v-1);
            a[v-1].push_back(u-1);
        }
        for(i=0;i<n;i++) scanf("%d",&value[i]);

        if(n<2)
        {
            printf("0\n");
            return 0;
        }

        for(i=0;i<n;i++)
        {
            if(!mark[i])
            {
                mini=10000000;
                dfs(i);
                if(mini==10000000)
                flag=1;
                else
                x.push_back(mini);
            }
        }

        if(flag==1)
        {
            printf("-1\n");
        }
        else
        {
            for(i=0;i<x.size();i++)
            {
                sum= sum+ x[i];
                if(x[i]<minx)minx= x[i];
            }

            sum+= (x.size()-2)*minx;
            printf("%lld\n",sum);

        }
    return 0;
}

asked 16 Jul '13, 09:26

shashank_1's gravatar image

1★shashank_1
4114
accept rate: 0%

edited 22 Jul '13, 05:03

gamabunta's gravatar image

1★gamabunta
2.4k128183169


@shashank_1: there were two bugs in your code: 1. when the whole graph visited in one go, u was still printing -1, instead of 0(that u fixed probably,actually I am not able to access your latest ideone submission). 2. the second bug is that, u have not initialized the variable minx, with any max_value before making the comparison.

Below is the link of your modified code, which got AC. http://www.codechef.com/viewsolution/2384944

link

answered 17 Jul '13, 00:21

ravishanker's gravatar image

3★ravishanker
18126
accept rate: 33%

Check your output for this test case:

2 1

1 2

-1

-2

Your Output : -1

Correct Output: 0

link

answered 16 Jul '13, 10:58

vagrawal13's gravatar image

2★vagrawal13
152
accept rate: 0%

You must end your program after you print -1...your program seems to continue to print other values after printing -1.

link

answered 16 Jul '13, 19:34

amitrc17's gravatar image

5★amitrc17
62116
accept rate: 0%

@shashank_1...your code fails for this testcase

INPUT:

3 2
2 3
1 2
-1 
-1
-1

This is because...If there is ONE compenent in the graph and all are interconnected then there is not need to build any teleport hence the o/p should be 0 instead of -1.Hope this helps.:D

link

answered 16 Jul '13, 22:35

rahul_nexus's gravatar image

2★rahul_nexus
7741923
accept rate: 13%

http://ideone.com/S9DpAw

still giving WA

link

answered 16 Jul '13, 19:22

shashank_1's gravatar image

1★shashank_1
4114
accept rate: 0%

link

answered 16 Jul '13, 21:56

shashank_1's gravatar image

1★shashank_1
4114
accept rate: 0%

thnx @ravishanker u r right , thnx a lot..

bcoz of u, i m able to noe my mistake and correct it nw i hv done dis ques using disjoint-set structure http://www.codechef.com/viewsolution/2385176

link

answered 17 Jul '13, 02:56

shashank_1's gravatar image

1★shashank_1
4114
accept rate: 0%

@shashank_1: thnks, good going :)

(17 Jul '13, 09:38) ravishanker3★

here is the link to my solution http://www.codechef.com/viewsolution/5478497 gettin right answer for all above testcases bt getting WA plz help

link

answered 02 Dec '14, 02:49

nidhisingh779's gravatar image

2★nidhisingh779
314
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×302

question asked: 16 Jul '13, 09:26

question was seen: 1,058 times

last updated: 02 Dec '14, 02:49