## 793 - Network Connections

Moderator: Board moderators

hint4:
There is still a bug in connect(int, int)

Code: Select all
`23c 1 3c 1 22c 1 1q 1 2`

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

### asd

ok..i've got it now...silly bug...

thanks for ur help...
darkos32
New poster

Posts: 27
Joined: Tue Jul 25, 2006 8:10 am
Location: Indonesia

### 793 WA Help~~

My code worked fine for every test case I found here, but I still get WA.
Can someone help me?

Here is my code:
Code: Select all
`removedI got AC.`

Thanks.
l314
New poster

Posts: 7
Joined: Sun Jan 28, 2007 9:53 am

Why RE?

Code: Select all
`#include <stdio.h>int *pai, *rank;void MakeSet(int x);int FindSet(int x);void UnionSet(int x, int y);int main(){    int num, num1, num2, casos, sim, nao, flag = 0;    char c;    scanf("%d\n", &casos);    while (casos--)    {        if (flag == 1)        {            printf("\n");        }        else        {            flag = 1;        }        sim = 0;        nao = 0;        scanf("%d\n", &num);        rank = (int *) calloc(num + 1, sizeof(int));        pai = (int *) calloc(num + 1, sizeof(int));        while (num--)        {            MakeSet(num);        }        scanf("%c %d %d\n", &c, &num1, &num2);        while (1)        {            scanf("%c", &c);            if (c == 'c')            {                scanf("%d%d\n", &num1, &num2);                UnionSet(num1, num2);            }            else if (c == 'q')            {                scanf("%d%d\n", &num1, &num2);                if (FindSet(num1) == FindSet(num2))                {                    sim++;                }                else                {                    nao++;                }            }            if (feof(stdin))            {                break;            }        }        printf("%d,%d\n", sim, nao);    }}void MakeSet(int x){    pai[x] = x;    rank[x] = 0;}int FindSet(int x){    if (x != pai[x])    {        pai[x] = FindSet(pai[x]);    }    return pai[x];}void UnionSet(int x, int y){    x = FindSet(x);    y = FindSet(y);    if (x == y)    {        return;    }    if (rank[x] > rank[y])    {        pai[x] = y;        rank[y] += rank[x];    }    else    {        pai[y] = x;        rank[x] += rank[y];    }}`

Thanks.
renato_ferreira
New poster

Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm

### Getting WA

I got WA..
What's the problem??

Here is my code:

Code: Select all
`I have a simple mistake....Delete After ACC...`

Amra korbo joy akhdin............................
mohsincsedu
Learning poster

Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka

### Re: 793 - Network Connections

I am getting WA for this problem . Could anyone can help me by some critical input/output??

I also mention my code here; If can, then check it up:
Code: Select all
`#include<cstdio>#include<cmath>#include<cstdlib>#include<cstring>#include<string>#include<iostream>#include<map>using namespace std;#define MAX(a,b)  ((a>b)?a:b)#define MIN(a,b)  ((a<b)?a:b)const int limits=1000010;int ar[limits];int main(){   //freopen("in.txt","rt",stdin);   //freopen("out.txt","wt",stdout);      int test,q,n,x,y,p1,p2,temp,a,b,suc,unsuc;   char ques[100],input[600];   map<int,int> mp;      scanf("%d",&test);   while(test--)   {      scanf("%d\n",&q);      n=1;      suc=0;      unsuc=0;      while(gets(input) && sscanf(input,"%s %d %d",ques,&a,&b)==3)      {         x=0; y=0;         if(ques[0]=='c')         {            if(mp.find(a)==mp.end())            {               mp[a]=n;               x=n;               n++;            }            if(mp.find(b)==mp.end())            {               mp[b]=n;               y=n;               n++;            }            if(x!=0&&y!=0)            {               ar[x]=y;               ar[y]=y;            }            else if(x==0&&y==0)            {               x=mp[a];               y=mp[b];               p1=x;               while(ar[p1]!=p1)                  p1=ar[p1];               p2=y;               while(ar[p2]!=p2)                  p2=ar[p2];               if(p1!=p2)               {                  temp=MAX(p1,p2);                  ar[p1]=temp;                  ar[p2]=temp;                  ar[x]=temp;                  ar[y]=temp;               }               else               {                  //printf("%d\n",cost[p1]);                  ar[x]=p1;                  ar[y]=p1;               }            }            else            {               if(x==0)               {                  x=mp[a];                  p1=x;                  while(p1!=ar[p1])                     p1=ar[p1];                  ar[x]=p1;                  ar[y]=p1;               }               else if(y==0)               {                  y=mp[b];                  p2=y;                  while(p2!=ar[p2])                     p2=ar[p2];                  ar[x]=p2;                  ar[y]=p2;               }            }         }         else if(ques[0]=='q')         {            if(mp.find(a)!=mp.end() && mp.find(b)!=mp.end())            {               x=mp[a];               y=mp[b];               p1=x;               while(p1!=ar[p1])                  p1=ar[p1];               p2=y;               while(p2!=ar[p2])                  p2=ar[p2];               if(p1!=p2)                  unsuc++;               else                  suc++;            }            else               unsuc++;         }      } // end of while loop      printf("%d,%d\n",suc,unsuc);      if(test)         printf("\n");      mp.clear();   }   // End of main function........return 0;}`
I like programming but i am so lazy to do it...

Oronno
New poster

Posts: 21
Joined: Sun Jul 09, 2006 1:42 pm
Location: Dhaka

### Re: 793 - Network Connections

Why WA plz help

Code: Select all
`#include <cstdio>#include <algorithm>#define MAX 10000using namespace std;int set[MAX];void setSet(int n){   int i;   for(i = 0; i < n; i++)      set[i] = i;}int findSet(int n){   return set[n];}void setReset(int a,int b,int max){   int i;   int t = set[a];   for(i = 0; i < max; i++){      if(set[i] == t)         set[i] = set[b];   }}int main(){   //freopen("in.txt","rt",stdin);   int test,i,N,a,b;   char c;   int noRight,noWrong;      scanf("%d",&test);   for(i = 0; i < test; i++){      noRight = noWrong = 0;      scanf("%d%*c",&N);      setSet(N);      while(scanf("%c %d %d%*c",&c,&a,&b) == 3){         if(c == 'c')            setReset(a,b,N);         else if(c == 'q'){            if(findSet(a) == findSet(b))               noRight++;            else               noWrong++;         }      }      if(i)         puts("");      printf("%d,%d\n",noRight,noWrong);   }   return 0;}`

newton
Experienced poster

Posts: 162
Joined: Thu Jul 13, 2006 7:07 am

### 793 - Network Connections WA a lot

Code: Select all
`code removed after acc`
alamgir kabir
New poster

Posts: 37
Joined: Wed Oct 03, 2007 10:42 am

### WA: 793 - Network Connections

What's wrong in my code.I check all input test given in the board. But still WA.Can anyone plz help me.
Code: Select all
`// Union finding-793#include<stdio.h>#include <string.h>#include <stdlib.h>long p[1000000];long parent(long x){    if(p[x]==-1)        return x;    else{        p[x]=parent(p[x]);        return p[x];    }}int main(){    long i,n,N,unsuccess,success,p1,p2,test=1,num[1000];   char s[5000],*t,ch;    scanf("%ld",&n);   getchar();   getchar();    while(n--)    {      if(test!=1)      {         printf("\n");      //   getchar();      }      scanf("%ld",&N);         for(i=0;i<=N;i++)      {            p[i]=-1;        }      unsuccess=0;success=0;      getchar();      while(gets(s))      {            ch=s[0];         s[0]='1';         i = 0;         t = strtok(s," ");                     while(t)         {            sscanf(t,"%ld",&num[i]);            i++;            t = strtok(NULL," ");         }         p1=parent(num[1]);         p2=parent(num[2]);         if(ch=='c')         {                  if(p1!=p2)               p[p1]=p2;         }         else if(ch=='q')         {            if(p1!=p2)               unsuccess++;            else               success++;         }      }               printf("%ld,%ld\n",success,unsuccess);      test++;    }    return 0;} `
New poster

Posts: 18
Joined: Sun Jan 24, 2010 11:17 am

### Re: 793 - Network Connections

I tried a lots of input sets and my algo gives correct output but still WA. Is there any thing i am not noticing????
New poster

Posts: 17
Joined: Tue Dec 22, 2009 4:20 pm

### Re: 793 - Network Connections

Got AC after 3 TLE and 3 WA.
New poster

Posts: 17
Joined: Tue Dec 22, 2009 4:20 pm

### Re: 793 - Network Connections

Code: Select all
`Accepted :)`
Last edited by Alice_Italy on Wed Sep 26, 2012 9:53 pm, edited 1 time in total.
Alice_Italy
New poster

Posts: 7
Joined: Thu Sep 20, 2012 6:47 am

### Re: 793 - Network Connections

init() needs to initialize pset[1] through pset[n].
brianfry713
Guru

Posts: 1755
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 793 - Network Connections

brianfry713 wrote:init() needs to initialize pset[1] through pset[n].

Thank you so much
Alice_Italy
New poster

Posts: 7
Joined: Thu Sep 20, 2012 6:47 am

### Re: 793 - Network Connections

I hate print blank line between test case so much. Judge will say WA instead of PE, which leads you to a wild goose chase.
achan8501
New poster

Posts: 6
Joined: Mon Nov 05, 2012 9:13 pm

Previous