OJ Board

Posted: **Fri Sep 17, 2004 8:36 pm**

Using this algo i got A.C for 459 , 793 ,10227 . But why TLE for 10608
Can anyone help?
thanks in advance.

Posted: **Fri Sep 17, 2004 9:32 pm**

dont use

while(scanf("%d",&test)==1)
{
while(test)
{
test--;
}
}

instead use

scanf("%d",&test);

while(test)
{
test--;
}

but thus u can escape from tle,but still your code holds a bug and getting WA.check it out.

Posted: **Sat Jan 15, 2005 5:16 pm**

I'm getting W.A.

Don't Know why .

I tested the program with a lot of inputs, and the answers were correct.

I will really appreciate some test cases...

I'm also posting my code:

// CUT

THANK YOU VERY MUCH !!!

Posted: **Mon Jan 17, 2005 4:24 pm**

It seems that you are using sets to divide the members into groups..
And the implementation of that is a little complicated and thus error prone.

.. but you can easily solve this problem using bfs/dfs.

Posted: **Mon Jan 17, 2005 7:29 pm**

Thanks for your help Sohel.

But the problem is how should I represent the graph while using BFS of DFS.

Both the adjacency matrix and adjacency list representation may lead to a 30000*30000

memory requirements as there are 30000 vertexes (30000 people);

Thats why I used this method.

Give me a hint

PS: If anybody has solved this code, Please give me some TEST CASES.

THANK YOU VERY MUCH !!!

Posted: **Tue Jan 18, 2005 8:33 am**

tomal wrote: Both the adjacency matrix and adjacency list representation may lead to a 30000*30000 memory requirements as there are 30000 vertexes (30000 people);

Using Adjacency matrix will certainly get MLE/TLE, but the usage of adjacency list will suffice. There might be 30000 different vertices but there wont be cases where you have to handle 30000*30000 memory.

Remember there can be at most 500000 different pairs and that is not a lot.

You can use STL Vector to represent the matrix.. ( if you don't already know it) and then run a dfs.

Hope this will help you in some way.

Posted: **Tue Jan 18, 2005 9:56 pm**

Code: Select all

for(k=1;k<=n;k++)if(a[k]==a[j])a[k]=a[i];

this line is wrong. you should use a temporary variable for the value of a[j], since with this loop you are changing a[j] to a, so if there are values a[k] == a[j] with k>j, you will forget to set them to the new value a.
Btw, why didn't you use the union find data structure? It is much faster.

Posted: **Thu Jan 20, 2005 6:09 am**

I got Acc.

Thank you Adrian Kuegel, I was so blind

!!!

Posted: **Thu May 26, 2005 8:29 am**

I've tried many datas,and it's correct......But I got W.A. >"<
Please help me!!Thanks a lot!!

Code: Select all

/*Q10608: Friends*/
/*2005.5.25   W.A.*/
#include<stdio.h>

int main()
{
    int i,j,n,a,b,c[30001],x,y,num,t[30001],max;
    
    scanf("%d",&n);
    while(n--){
        for(i=0;i<30001;i++){ c[i]=0; t[i]=0; }
        scanf("%d %d",&a,&b);
        num=0;
        while(b--){
           scanf("%d %d",&x,&y);
           if(c[x]){ 
               if(!c[y]){c[y]=c[x]; t[c[x]]++;}
               else if(c[x]!=c[y]){
                   t[c[x]]+=t[c[y]];
                   for(j=1;j<=a;j++)
                     if(c[j]==c[y]) c[j]=c[x];
               }
           }
           else{
              if(c[y]){ 
                  if(!c[x]){c[x]=c[y]; t[c[y]]++;}
                  else if(c[x]!=c[y]){
                      t[c[y]]+=t[c[x]]; 
                      for(j=1;j<=a;j++)
                          if(c[j]==c[x]) c[j]=c[y];
                  }
              }
              else{
                 num++;
                 c[x]=c[y]=num; t[num]=2;
              }
           }
        }
        max=0;
        for(i=1;i<=num;i++)
            if(t[i]>max) max=t[i];
        printf("%d\n",max);
    }

    return 0;
}

Posted: **Wed Jun 01, 2005 3:36 pm**

Hi, liang1425 !

I've sent you a private message with your fixed code.

It will get ACC

if you submit it.

Regards !

Posted: **Sat Jun 04, 2005 7:14 pm**

Dear Sedefcho~
Thank you very much:)
I've known where my code was wrong.
Thank you.

Posted: **Thu Jun 16, 2005 10:20 am**

I'm getting W.A. Don't Know why .

I post the code

Code: Select all

#include <cstdio>
#include <cstdlib>

int parent[30001];
int count[30001];

int main() {
    int t, m, n, a, b, Max;

    scanf("%d\n", &t);

    for (int i=0;i<t;i++) {
        scanf("%d %d\n", &m, &n);

        for (int j=1;j<=m;j++) {
            parent[j] = j;
            count[j] = 0;
        }

        for (int j=0;j<n;j++) {
            scanf("%d %d\n", &a, &b);

            while (parent[a] != a) {
                a = parent[a];
            }
            
            while (parent[b] != b) {
                b = parent[b];
            }

            if (a<b) {
                parent[b] = a;
            }
            else {
                parent[a] = b;
            }
        }

        for (int j=1;j<=m;j++) {
            count[parent[j]]++;
        }
        
        /*for (int j=1;j<=m;j++) {
			printf("%d ", count[j]);
		}
        putchar('\n');*/
        
        Max = 0;
       
        for (int j=1;j<=m;j++) {
            if (count[j] > Max) {
                Max = count[j];
            }
	    }

        printf("%d\n", Max);
    }
}

Posted: **Sat Jun 18, 2005 5:31 am**

nobody know ?

Posted: **Tue Jun 28, 2005 12:44 am**

Anyone know what wrong in my code???

Posted: **Tue Jul 19, 2005 7:52 pm**

You need to move all of b's friends to a's group or the other way, not just b or a:

Input:

Code: Select all

Output:

Code: Select all

OJ Board

10608 - Friends

10608 : why this code gives T.L.E

10608

10608 W.A. [Why?] HELP!!!

there is a easier way..

10608

Got AC

10608WA

10608 WA Why???

what is wrong with your code