## 793 - Network Connections

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

Moderator: Board moderators

What is the output for the following input set... Can anyone tell me..

Code: Select all
`1 5c 1 3c 3 4c 4 5q 1 2q 3 4q 1 5q 3 5`

Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

Riyad, I think this is a multiple input problem. And for this, u have to initialize p[] for every input set. Otherwise for same input set more than once u will get different answers.

And another thing, in your code I found...

Code: Select all
`m=p[x]; n=p[y];    p[y]=n;  //No meaning, I think it should be p[x]=n`

Hope it works...
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

### 793 - TLE (C++)

Is there a better way to solve this question?

Code: Select all
`#include<iostream>using namespace std;///////////////////////////////////////////////////////////////////////////////typedef struct _set{  int v,t;}PG;PG s[1001];void makeset(PG* s,int smax) {  for(int i=1;i<=smax;i++){s[i].v=i;s[i].t=i;}}int find(PG *s,int a)  {  while(s[a].t!=a)a=s[a].t;  return a;}void merge(PG *s,int a,int b)  {  a=find(s,a);b=find(s,b);  if(a<b)s[b].t=a;  else s[a].t=b;}bool same(PG *s,int a,int b){  if(find(s,a)==find(s,b))return true;  else return false;}void print_s(PG *s,int smax){  for(int i=1;i<=smax;i++)cout<<s[i].v<<" "<<s[i].t<<endl;}///////////////////////////////////////////////////////////////////////////////int main(){  int qmax,cmax,y,n;  int t1,t2;  char ch;  cin>>qmax;  for(int qi=1;qi<=qmax;qi++)  {      y=n=0;      cin>>cmax;      makeset(s,cmax);      cin.get();      while(1)      {          ch=cin.peek();          if(ch=='\n')break;          cin.get();          cin>>t1>>t2;          if(ch=='c')              merge(s,t1,t2);          if(ch=='q')          {              if(same(s,t1,t2))y++;              else n++;          }          cin.get();      }      cout<<y<<","<<n<<endl<<endl;  }}`
PG
New poster

Posts: 4
Joined: Mon Nov 14, 2005 7:16 am

3,1
Wei-Ming Chen
Experienced poster

Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

### 793 TLE

I thought my code is fast, but TLE.....

Can someone tell me why?

No it's slow

DO NOT use DFS in this problem
Last edited by Wei-Ming Chen on Sat Jul 15, 2006 6:39 pm, edited 1 time in total.
Wei-Ming Chen
Experienced poster

Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

### 793 why WA!?

Why WA!?
I can't find my bug...

Code: Select all
`I have got AC!`
IRA
Learning poster

Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

Thanks, got Accepted...
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

I use same method(disjoint-set) and got it. maybe you should check before merging that if two sets are equal or not
Moha
Experienced poster

Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran

### 793...TLE with Union-find data structure???

isnt this algo enogh for this is proble??
plz help me

Code: Select all
`removed`

thnx for helping
Last edited by asif_rahman0 on Wed Apr 26, 2006 9:26 pm, edited 1 time in total.
asif_rahman0
Experienced poster

Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

You didn't test the connection before make a connection. your program may be create a cycle.
Moha
Experienced poster

Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran

### 793.... really strange??

can someone tell me about multiple I/O??
i m getting TLE because of this thing. so plz reply me back so that i can get accepted.

Code: Select all
`removed`
Last edited by asif_rahman0 on Tue May 09, 2006 10:47 pm, edited 1 time in total.
asif_rahman0
Experienced poster

Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

asif_rahman0
Experienced poster

Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

asif_rahman0 wrote:still no reply:(

Only about 2 hours have passed between your 2 posts. Think, you are too optimistic.

asif_rahman0 wrote:can someone tell me about multiple I/O??

Read this - http://acm.uva.es/problemset/minput.html
AFAIK now all problem descriptions are described such. Read the same problem statement at http://acm.uva.es/p/v7/793.html

asif_rahman0 wrote:i m getting TLE because of this thing.

I don't think so.
mamun
A great helper

Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm

mamun vai,
i submitted this problem many times. but when i read input with EOF then i got WA. and If not then TLE.

i m sure that i wont get TLE at all if the input file isnt too big.
my algo is good enough.
ok
so plz reply me how to get rid of from TLE??
asif_rahman0
Experienced poster

Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Hey man,
I had problems with EOF too, but this worked:

Code: Select all
`scanf("%d\n",&T);   while(T--){      scanf("%d\n",&n);      rank=malloc((n+1)*sizeof *rank);      p=malloc((n+1)*sizeof *p);      for(i=1;i<=n;i++)         make_set(i);      n1=n2=0;      while(gets(s)!=NULL && sscanf(s,"%c %d %d",&ch,&i,&j)==3){      /*blah-blah/*                            }feof(stdin))                                           break;                        }`

You use union-find?
Last edited by serur on Sat Apr 14, 2012 3:30 pm, edited 1 time in total.
serur
A great helper

Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

PreviousNext

### Who is online

Users browsing this forum: No registered users and 1 guest