793  Network Connections
Moderator: Board moderators
As far as your input is concerned you'll not get TLE but WA. Test this case
There is no specification about the input range. So no idea how many vertices you have to deal with. Maybe even large enough to fit in your 10 sized s1 and s2 arrays! Calling DFS so many times will cause TLE.
Use dijsoint sets.
Code: Select all
1
10
c 2 5
q 2 5
Use dijsoint sets.

 Experienced poster
 Posts: 209
 Joined: Sun Jan 16, 2005 6:22 pm
above input is now ok. and also others input/output. Any more I/O!!!
now i m getting WA..... so sad!!!
plz help
now i m getting WA..... so sad!!!
plz help
Code: Select all
removed
Last edited by asif_rahman0 on Wed May 10, 2006 4:37 am, edited 1 time in total.
A very straightforward input to show your error
Code: Select all
2
2
c 1 2
q 1 2
3
c 1 3
q 1 2

 Learning poster
 Posts: 83
 Joined: Wed Feb 01, 2006 12:59 pm
 Location: (Fcicu) Egypt
 Contact:
Salamo Aleko.
Sorry i do not like reading codes...
But this is a good advice....
In many contests you may face diffrent problems like this, trying every time to make good and fast algorithm is not some thing good.
There is a algorithm called "Union Find operation with path compression"
This is the fastest know lgorithm for Union Find operation. Moreover it is to simple. You can find the full source code in this book
"Introduction to algorithms"
You can solve with it efficiently the next problems
"793 10583 10685 10608 615"
Sorry i do not like reading codes...
But this is a good advice....
In many contests you may face diffrent problems like this, trying every time to make good and fast algorithm is not some thing good.
There is a algorithm called "Union Find operation with path compression"
This is the fastest know lgorithm for Union Find operation. Moreover it is to simple. You can find the full source code in this book
"Introduction to algorithms"
You can solve with it efficiently the next problems
"793 10583 10685 10608 615"
Sleep enough after death, it is the time to work.
Mostafa Saad
Mostafa Saad
I've used my faulty unionfind to solve a few problems, but this one made me realize that it doesn't work quite the way I thought it would.
Here's a case on which my implementation is failing:
Output should be
P.S. Instead of C&P I retyped it and that caused its faultiness, it was ok all along.
Here's a case on which my implementation is failing:
Code: Select all
1
9
c 3 9
c 1 6
c 4 8
c 3 2
c 3 8
c 5 7
c 6 2
c 5 4
q 9 1
q 4 8
Code: Select all
2,0

 Experienced poster
 Posts: 122
 Joined: Sun Nov 13, 2005 10:25 am
 Location: Taiwan
793  WA
My code worked fine for every test case i found here, but i still get WA.
Can someone help me?
Here is my code:
Thanks.
Can someone help me?
Here is my code:
Code: Select all
#include <stdio.h>
#define max 1000
int m[max][max], d[max];
int fila[max], inicio, fim;
int suc, unsuc;
void adiciona(int a, int b) {
int i;
for (i = 1; i <= m[a][0]; i++)
if (m[a][i] == b) break;
if (i = m[a][0]+1) {
m[a][++m[a][0]] = b;
m[b][++m[b][0]] = a;
}
}
void colocanafila(int n) {
fila[fim++] = n;
if (fim > (max1)) fim = 0;
}
int retiradafila() {
int ret;
if (inicio == fim) ret = 1;
else ret = fila[inicio++];
if (inicio > (max1)) inicio = 0;
return ret;
}
void bfs(int a, int b) {
int i, w;
memset(d, 1, sizeof(d));
d[a] = 1;
inicio = fim = 0;
w = a;
while (w != 1) {
for(i = 1; i <= m[w][0]; i++) {
if (d[m[w][i]] == 1) {
if (m[w][i] == b) {
suc++;
w = 0;
break;
}
else {
d[m[w][i]] = 1;
colocanafila(m[w][i]);
}
}
}
if (!w) break;
w = retiradafila();
}
if (w == 1) unsuc++;
}
int main()
{
int t, n, q, w, first=1;
int ci, cj;
char tipo[2];
scanf("%d", &t);
while (t) {
if (first) first = 0;
else printf("\n");
t;
memset(m, 0, sizeof(m));
suc = unsuc = 0;
scanf("%d", &n);
while (scanf("%s %d %d\n", tipo, &ci, &cj) == 3) {
switch (tipo[0]) {
case 'c': adiciona(ci, cj); break;
case 'q': bfs(ci, cj); break;
}
}
printf("%d,%d\n", suc, unsuc);
}
return 0;
}

 New poster
 Posts: 2
 Joined: Sat Oct 14, 2006 9:52 pm
There is a great article about "Union Find operation" algorithm here:
http://valis.cs.uiuc.edu/~sariel/teach/ ... /22_uf.pdf
http://valis.cs.uiuc.edu/~sariel/teach/ ... /22_uf.pdf
793 RUNTIME ERROR SIGNAL 11 ?
Last edited by darkos32 on Wed Feb 14, 2007 8:38 am, edited 1 time in total.
hint:

!! Don't open a new thread if there is a thread already for the problem.
Code: Select all
#define max 200
!! Don't open a new thread if there is a thread already for the problem.
sad
yep...i've changed to 1000,but i'm now got WA...
hint2:
hint3:
There is a bug in connect(int, int).
Code: Select all
1
1
q 1 1
There is a bug in connect(int, int).
sad
i've changed the code to :
but i've still got WA...
Code: Select all
CODE REMOVED
Last edited by darkos32 on Wed Feb 14, 2007 9:04 am, edited 1 time in total.