459 - Graph Connectivity

[saiful_sust]

I got ACC.........
taking input is the problem ...........
ugly input format.........

[Igor9669]

Input terminated by EOF!!!! Not by blank line! When I change it I got AC!

[Obaida]

Code: Select all

removed...

[Mehadi]

Thanks Igor9669 really ugly output format.Finally AC after 4 TLE & 1 WA

[mustak]

My Code gets WA to the judge, I don't understand where is the problem. Please help me. Here is my code :

Code: Select all

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

long p[30001];

long parent(long x)
{
  if(p[x]==-1)
  return x;
  else{
  p[x]=parent( p[x]);
  return p[x];
  }
}

int main()
{
 long l,t,i,k,a[100],p1,p2,j,q,f;
 char c[1000000],s[1000000];
 
 cin>>t;
 getchar();
 getchar();
 
 for(k=0;k<t;k++)
 {
  gets(c);
  //getchar();
  
  remove(c,c+strlen(c),' ');
  
  for(i=0;i<=c[0]-'A';i++)
  {
   p[i]=-1;
   a[i]=0;
  }
 
  
  while(gets(s))
  {
   if(s[0]=='\0')
   break;             
   remove(s,s+strlen(s),' ');
   p1=parent(s[0]-'A') ;
   p2=parent(s[1]-'A') ;
   if(p1!=p2)
   p[p1]=p2;         
  }
  l=0;f=0; 
  for(i=0;i<=c[0]-'A';i++)
  {
   q=parent(i);
   for(j=0;j<l;j++)
   {
    if(a[j]==q)
    {
     f=1;
     break;           
    }                
   }
   if(f==0)
   {
    a[l]=q;
    l++;
   }
   f=0;                 
  }
  
  
  
  cout<<l<<endl;
  if(k!=t-1)
  cout<<endl;               
  getchar();               
 }   
    
 return 0;    
}

[helper]

The input format for this problem is really very confusing ... i spend lot of time in this .. i am posting my way of taking input for someone's help

Code: Select all

#include<stdio.h>
#include<stdlib.h>

int parent[1000];
int node[150];
char s[100000];

void reset(int n);

int main(){

	int i,j,k,test,count,n,res1,temp;
	bool blank=false;
	char dum,help[5],bfr[100];

    

	scanf("%d%c",&test,&dum);
	getchar();

	while(test--){

		do{
			gets(bfr);
		}while(!bfr[0]);

		n=bfr[0];

		reset(n);

		while(gets(s)){

			if(!s[0]) break;
			
             temp=parent[s[1]];
						
		}

         //  Your  Algo  here.............

		
	}

	return 0;

}

hope it helps

[SyFyKid]

realy crazy output
had to submit for 100500 time ... LAST line should be empty in your output.

I thought that the problem was in reading input... but its ok.
first you can read all input data except empty lines... after that - parse it and solve.

example from my code:

Code: Select all

ArrayList<String> input = new ArrayList<String>();
        String line;

        // input
        while(true){
            line = RLine();

            if(line == null) break;
            if(line.trim().isEmpty()) continue;

            input.add(line.trim());
        }

and I finally got AC.

good luck!

[mahade hasan]

cut>>

[brianfry713]

Find() looks slow.

[mahade hasan]

Find() looks slow.

Edited but still TLE.....

[brianfry713]

Post your updated code if you want.

[mahade hasan]

cut>>>>>>

[brianfry713]

Change line 24 to:
if(gets(Input)==NULL) break;

[mahade hasan]

Change line 24 to:
if(gets(Input)==NULL) break;

when i change this line got RE.............

[brianfry713]

Post your updated code if you want. I took the code you posted most recently, changed the one line as I described, and got AC.