793 - Network Connections

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
rodriwan
New poster
Posts: 8
Joined: Mon Jun 03, 2002 8:13 pm

793 - Network Connections

Post by rodriwan » Mon Jun 03, 2002 8:35 pm

Hi, Im trying to send the folowing code, but I am geting wrong answear, I cant find where Im wrong... Im using quickfind algorithm, can anyone help?

[c]
"@BEGIN_OF_SOURCE_CODE"
/* @JUDGE_ID: xxxxxx 793 C */
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>

typedef unsigned long mytype;

int
main(int argc, char **argv)
{
char op;
mytype p, q, N;
mytype i, j;
mytype conected, unconected;
mytype *id;
char buff[500];

char getop(void);
void unionid(mytype *id, mytype p, mytype q, mytype N);
int find(mytype *id, mytype p, mytype q);

scanf("%ld", &N);

/* inicializa os vetores que conterao
* os logs da coneccao */
id = (mytype *) calloc(N+1, sizeof(mytype));
for (i = 1; i <= N; i++)
id = i;

conected = unconected = 0;
while (fgets(buff, 500, stdin) != NULL) {
sscanf(buff, "%c %ld %ld", &op, &p, &q);
switch (op) {
case 'c': /* union */
if (!find(id, p, q))
unionid(id, p, q, N);
break;
case 'q': /* find */
if (find(id, p, q))
conected++;
else
unconected++;
break;
}
}
printf("%ld,%ld\n", conected, unconected);

return 0;
}

void unionid(mytype *id, mytype p, mytype q, mytype N)
{
mytype t, i;

for (t = id[p], i = 1; i <= N; i++)
if (id == t)
id = id[q];
}

int find(mytype *id, mytype p, mytype q)
{
return (id[p] == id[q]) ? 1 : 0;
}

"@END_OF_SOURCE_CODE"
[/c]

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

hmm

Post by Caesum » Tue Jun 04, 2002 10:57 am

this is a multiple input problem and you are not handling the input format correctly. read the notes on the format for multiple input (see the blue tick by the name of the problem ?). when thats fixed it will be accepted.

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

793

Post by htl » Sat Jul 13, 2002 5:59 pm

I check my code again and again. But it still got RE. I think the number of computers won't be bigger than 10000. Where are the bugs?
[c]
#include<stdio.h>
#include<string.h>
void unionfunc(int,int);
int find(int);
int parent[10000];
void main(void)
{
int count,x,i,j,n,y,yes,no,temp,rooti,rootj;
char c,buffer[50];
scanf("%d",&count);
for(x=0;x<count;x++)
{
if(x!=0)
printf("\n");
scanf("%d\n",&n);
for(y=0;y<n;y++)
parent[y]=-1;
yes=no=0;
while(1)
{
if(fgets(buffer,50,stdin)==NULL)
break;
buffer[strlen(buffer)-1]='\0';
if(!strlen(buffer))
break;
for(y=0;buffer[y]!='\0';y++)
if(buffer[y]>='0' && buffer[y]<='9')
break;
for(i=0;buffer[y]!=' ';y++)
i=i*10+buffer[y]-'0';
for(;buffer[y]!='\0';y++)
if(buffer[y]>='0' && buffer[y]<='9')
break;
for(j=0;buffer[y]!='\0';y++)
j=j*10+buffer[y]-'0';
if(buffer[0]=='c')
{
rooti=find(i-1);
rootj=find(j-1);
unionfunc(rooti,rootj);
}
else
{
rooti=find(i-1);
rootj=find(j-1);
if(rooti==rootj)
yes++;
else
no++;
}
}
printf("%d,%d\n",yes,no);
}
}
void unionfunc(int i,int j)
{
int temp;
temp=parent+parent[j];
if(parent>parent[j])
{
parent=j;
parent[j]=temp;
}
else
{
parent[j]=i;
parent=temp;
}
}
int find(int i)
{
int root,trail,lead;
for(root=i;;)
if(parent[root]>=0)
root=parent[root];
else
break;
for(trail=i;;)
if(trail!=root)
{
lead=parent[trail];
parent[trail]=root;
trail=lead;
}
else
break;
return root;
}
[/c]

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Mon Jul 22, 2002 5:53 pm

Could someone help me with the code? I really want to know if my code of find&union algo is correct.

obayashi
New poster
Posts: 33
Joined: Thu Jun 20, 2002 1:18 pm

793

Post by obayashi » Tue Aug 13, 2002 3:32 am

i use disjoint tree(Union() and Find()) to solve this problem but unfortunately i kept getting TLE :cry:
any one could be any of help?

here's the code
[cpp]
#include <iostream>
#include <string.h>
#include <stdlib.h>
#define myin cin
using namespace std;
int parent[1000],root[1000];
inline int Find (int e) {
int j = e, f = e, pf;
while (!root[j])
j = parent[j];
while (f!=j) {
pf = parent[f];
parent[f] = j;
f = pf;
}
return j;
}
inline void Union (int i,int j) {
int ri,rj;
ri = Find(i);
rj = Find(j);
parent[rj] = ri;
root[rj] = 0;
}
int main () {
int i,j,cas,n,s,t,con,discon;
char c,tmp[100],*p;
myin>>cas;
myin.getline(tmp,1);
myin.getline(tmp,1);
for (i=0;i<cas;i++) {
if (i>0)
cout<<endl;
myin>>n;
myin.getline(tmp,1);
for (j=0;j<=n;j++) {
parent[j] = 0;
root[j] = 1;
}
con = discon = 0;
while (1) {
myin.getline(tmp,99);
if (*tmp=='\0')
break;
p = strtok(tmp," \t\b\r\n");
c = *p;
p = strtok(NULL," \t\b\r\n");
s = atoi(p);
p = strtok(NULL," \t\b\r\n");
t = atoi(p);
if (c=='c') {
Union(s,t);
} else {
if (Find(s)==Find(t))
con++;
else
discon++;
}
}
cout<<con<<","<<discon<<endl;
}
return 0;
}

[/cpp]
Time makes a fool of memory
And yet my memories still shine

liusu
New poster
Posts: 22
Joined: Thu Aug 01, 2002 10:26 am

793

Post by liusu » Tue Aug 27, 2002 7:26 am

i try again and again,but still WA....... :oops: :oops: :oops:
please help.
thank you very much!!!!!!!!

[pascal]var
s:array[1..1000] of integer;
bool:array[1..1000] of boolean; //judge if it was connected
total:integer;

procedure inis(total:integer);
var
i:integer;
begin
for i:=1 to total do
begin
s:=i;
bool:=false;
end;
end;

procedure done;
var
su,un,i,total,m,n,tem:integer;
ch:char;
begin
su:=0;
un:=0;
readln(total);
inis(total);
read(ch);
while(ch='q')or(ch='c') do
begin
readln(m,n);
if(ch='c') then
begin
if (not bool[m])and(not bool[n]) then
begin
s[m]:=n;
bool[m]:=true;
bool[n]:=true;
end
else if(not bool[m]) then
begin
bool[m]:=true;
s[m]:=s[n];
end
else if(not bool[n]) then
begin
bool[n]:=true;
s[n]:=s[m];
end
else begin
if(s[m]<>s[n]) then
begin
tem:=s[m];
for i:=1 to total do
if s=tem then
s:=s[n];
end;
end;
end
else if(ch='q') then
begin
if(s[m]=s[n]) then inc(su)
else inc(un);
end;
read(ch);
end;
writeln(su,',',un);
// for i:=1 to total do
// writeln(i,' ',s);
writeln;
end;

begin
readln(total);
while (total>0) do
begin
done;
dec(total);
end;
end.[/pascal]

liusu
New poster
Posts: 22
Joined: Thu Aug 01, 2002 10:26 am

??

Post by liusu » Fri Aug 30, 2002 9:32 am

NO one can help me?What a pity.. :roll:

zsacul
New poster
Posts: 7
Joined: Sat Aug 17, 2002 8:11 pm
Location: Poland

793 why W.A.?

Post by zsacul » Fri Sep 27, 2002 11:24 pm

I have no more ideas what is wrong...
Alghoritm is simple union-find...
Can you help me?
:D
[cpp]
#include <stdio.h>
#include <assert.h>

int nr[2000];
unsigned long n;

void unionID(int what,int newID)
{
for (unsigned long i=0;i<n;i++)
{
if (nr==what) nr = newID;
}
}

bool question(unsigned long n1,unsigned long n2)
{
if (nr[n1-1]==nr[n2-1]) return true;
else return false;
}

int main(int argc, char **argv)
{
int mm;
scanf("%d\n",&mm);

for (int prob=0;prob<mm;prob++)
{
if (prob>0) printf("\n");
unsigned long n1,n2,i;
unsigned long odpCon = 0;
unsigned long odpNot = 0;
char c;

scanf("%d\n",&n);
assert(n<2000);

for (i=0;i<n;i++) nr=i;
scanf("%c %ld %ld\n",&c,&n1,&n2);

while ((c=='c')||(c=='q'))
{
assert( (c=='c')||(c=='q') );

if (c=='c')
{
if (!question(n1,n2)) unionID(nr[n1-1],nr[n2-1]);
}

if (c=='q')
{
if (question(n1,n2)) odpCon++;
else odpNot++;
}
c = 0;
scanf("%c %ld %ld\n",&c,&n1,&n2);
}

printf("%ld,%ld\n",odpCon,odpNot);
}

return 0;
}
[/cpp]

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

Post by Picard » Sat Sep 28, 2002 6:59 am

the input reading has an error. after the last 'c'/'q' line you read into the next input block because scanf("\n") reads more newline chars (and the next "scanf("%d\n",&n);" will fail).
i used (instead of the two scanf("%c ...)
[cpp]char s[256];
while (gets(s) && sscanf(s," %c %d %d",&c,&n1,&n2)==3)[/cpp]

zsacul
New poster
Posts: 7
Joined: Sat Aug 17, 2002 8:11 pm
Location: Poland

Post by zsacul » Sun Sep 29, 2002 1:58 pm

Thank you, I've got accepted! :D

User avatar
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

793

Post by yahoo » Fri Nov 29, 2002 2:25 pm

I can't understand how i can take input in this problem. I have tried with scanf but it seems not to work. Please help me.

ec3_limz
Learning poster
Posts: 79
Joined: Thu May 23, 2002 3:30 pm
Location: Singapore

input

Post by ec3_limz » Thu Dec 12, 2002 12:07 pm

Hi,

This type of problems are pretty irritating when it comes to input.

Here's how to do the input. Input the test case line by line into a string, and use a "string reader" to read the input from the string.

If you are using C (like me), you use the function gets(str) to input the line into a string str, and then you use the function sscanf(str, ...), to read input from str.

If you are using standard C++ classes, use the cin.getline() function to read in the line, and use the istrstream stream (found in <strstream>) to read input from a line.

To detect an end in the test case, simply test for (feof(stdin) || strlen(str)==0) if you're using C, or (cin.eof() || str.length()==0) if you're using standard C++ classes.

Hope this helps.

User avatar
Angel
New poster
Posts: 8
Joined: Wed Nov 20, 2002 3:49 pm

793 Help [WA] ???????????

Post by Angel » Tue Jul 29, 2003 12:27 am

what is the input terminating condition ??
I considered it as a blank line....
but Got WA .... Whats wrong here .....plz help me ....
here's my code....

#include<stdio.h>
#include<string.h>

void input();
void search();

int N,i,src,dst,G[100][100],yes,no,flag;
char ch,ins,A[6];


void main(void)
{


scanf("%d\n",&N);
{
yes=0;no=0;

while(gets(A))
{
if(A[0]!='q'&&A[0]!='c')break;
src=A[2]-48;
dst=A[4]-48;
if(A[0]=='c')input();
else search();
}
printf("%d,%d\n",yes,no);
}
}


void input()
{
G[src][dst]=1;
G[dst][src]=1;
}

void search()
{
flag=0;
if(G[src][dst]==1)yes++;
else
{
for(i=1;i<=N;i++)
{
if(G[src])
{
if(G[dst])
{
flag=1;
yes++;
}
else
{
flag=1;
no++;
}
}

}
if(flag!=1)no++;
}
}

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue Jul 29, 2003 9:25 am

The total number of test case is as indicated by N, the last set ends at EOF and not a newline.

User avatar
Angel
New poster
Posts: 8
Joined: Wed Nov 20, 2002 3:49 pm

plz check it again ...

Post by Angel » Tue Jul 29, 2003 11:39 am

I consider EOF .... while(gets(A))... wont it break at EOF ????
if not ... then how would I consider it .. ??? :-?
I test my program with freopen ... for the sample out put (without blank line...it means the loop is breaking at the EOF...is it ??? :-? )

Post Reply

Return to “Volume 7 (700-799)”