793 - Network Connections
Moderator: Board moderators
793 - Network Connections
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]
[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]
hmm
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.
793
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]
[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]
793
i use disjoint tree(Union() and Find()) to solve this problem but unfortunately i kept getting TLE
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]
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
And yet my memories still shine
793
i try again and again,but still WA.......
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]
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]
793 why W.A.?
I have no more ideas what is wrong...
Alghoritm is simple union-find...
Can you help me?
[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]
Alghoritm is simple union-find...
Can you help me?
[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]
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]
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]
input
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.
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.
793 Help [WA] ???????????
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++;
}
}
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++;
}
}
plz check it again ...
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 ??? )
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 ??? )