793 - Network Connections

[rio]

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]

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

thanks for ur help...

[l314]

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]

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]

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

[Oronno]

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;
}

[newton]

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]

Code: Select all

code removed after acc

[Mehadi]

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]

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]

Got AC after 3 TLE and 3 WA.

[Alice_Italy]

Code: Select all

Accepted :)

[brianfry713]

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

[Alice_Italy]

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

Thank you so much

[achan8501]

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.