793 - Network Connections

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Wed Feb 14, 2007 8:47 am

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

Code: Select all

2

3
c 1 3
c 1 2

2
c 1 1
q 1 2

darkos32
New poster
Posts: 27
Joined: Tue Jul 25, 2006 8:10 am
Location: Indonesia
Contact:

asd

Post by darkos32 » Wed Feb 14, 2007 9:05 am

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

thanks for ur help...

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

793 WA Help~~

Post by l314 » Thu Mar 01, 2007 4:54 pm

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

removed
I got AC.
Thanks.

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

Post by renato_ferreira » Wed Jun 27, 2007 11:06 pm

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.

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

Getting WA

Post by mohsincsedu » Thu Dec 20, 2007 11:17 pm

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

Here is my code:

Code: Select all

I have a simple mistake....
Delete After ACC...

Thanks in Advanced...
Amra korbo joy akhdin............................

User avatar
Oronno
New poster
Posts: 21
Joined: Sun Jul 09, 2006 1:42 pm
Location: Dhaka
Contact:

Re: 793 - Network Connections

Post by Oronno » Thu Oct 09, 2008 12:01 am

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...

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Re: 793 - Network Connections

Post by newton » Thu Apr 02, 2009 6:14 pm

Why WA plz help

Code: Select all

#include <cstdio>
#include <algorithm>
#define MAX 10000
using 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;
}
Thanks in advanced

alamgir kabir
New poster
Posts: 37
Joined: Wed Oct 03, 2007 10:42 am

793 - Network Connections WA a lot

Post by alamgir kabir » Tue Apr 21, 2009 9:13 pm

Code: Select all

code removed after acc

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

WA: 793 - Network Connections

Post by Mehadi » Thu May 20, 2010 4:28 pm

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;
}
 
[/color]

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

Re: 793 - Network Connections

Post by Rashad » Mon Sep 27, 2010 10:55 am

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

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

Re: 793 - Network Connections

Post by Rashad » Mon Sep 27, 2010 5:16 pm

Got AC after 3 TLE and 3 WA. :D

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

Re: 793 - Network Connections

Post by Alice_Italy » Wed Sep 26, 2012 7:50 am

Code: Select all

Accepted :)
Last edited by Alice_Italy on Wed Sep 26, 2012 9:53 pm, edited 1 time in total.

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

Re: 793 - Network Connections

Post by brianfry713 » Wed Sep 26, 2012 9:12 pm

init() needs to initialize pset[1] through pset[n].
Check input and AC output for thousands of problems on uDebug!

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

Re: 793 - Network Connections

Post by Alice_Italy » Wed Sep 26, 2012 9:53 pm

brianfry713 wrote:init() needs to initialize pset[1] through pset[n].
Thank you so much :D

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

Re: 793 - Network Connections

Post by achan8501 » Sun Dec 02, 2012 2:22 am

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.

Post Reply

Return to “Volume 7 (700-799)”