10608  Friends
Moderator: Board moderators
10608 : why this code gives T.L.E
Using this algo i got A.C for 459 , 793 ,10227 . But why TLE for 10608
Can anyone help?
thanks in advance.
Can anyone help?
thanks in advance.
Last edited by harry on Fri Sep 17, 2004 9:45 pm, edited 1 time in total.
 Ali Arman Tamal
 Learning poster
 Posts: 76
 Joined: Sat Jan 15, 2005 5:04 pm
 Location: Dhaka
 Contact:
10608 W.A. [Why?] HELP!!!
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 !!!
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 !!!
Last edited by Ali Arman Tamal on Mon Jan 31, 2005 3:34 pm, edited 2 times in total.
there is a easier way..
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.
And the implementation of that is a little complicated and thus error prone.
.. but you can easily solve this problem using bfs/dfs.
Last edited by sohel on Wed Jan 19, 2005 3:01 pm, edited 1 time in total.
 Ali Arman Tamal
 Learning poster
 Posts: 76
 Joined: Sat Jan 15, 2005 5:04 pm
 Location: Dhaka
 Contact:
10608
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 !!!
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 !!!
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.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);
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.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Code: Select all
for(k=1;k<=n;k++)if(a[k]==a[j])a[k]=a[i];
Btw, why didn't you use the union find data structure? It is much faster.
 Ali Arman Tamal
 Learning poster
 Posts: 76
 Joined: Sat Jan 15, 2005 5:04 pm
 Location: Dhaka
 Contact:
Got AC
I got Acc.
Thank you Adrian Kuegel, I was so blind !!!
Thank you Adrian Kuegel, I was so blind !!!
10608WA
I've tried many datas,and it's correct......But I got W.A. >"<
Please help me!!Thanks a lot!!
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;
}

 New poster
 Posts: 9
 Joined: Fri Jan 21, 2005 6:46 pm
10608 WA Why???
I'm getting W.A. Don't Know why .
I post the code
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);
}
}

 New poster
 Posts: 9
 Joined: Fri Jan 21, 2005 6:46 pm
what is wrong with your code
You need to move all of b's friends to a's group or the other way, not just b or a:
Input:
Output:
Input:
Code: Select all
1
10 5
1 2
2 3
4 5
5 7
3 4
Code: Select all
6