879 - Circuit Nets

All about problems in Volume 8. 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
CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

879 - Circuit Nets

Post by CDiMa »

Hi all.
I have a problem understanding the input specification.
The problem text says that the input is terminated by the "end_of_file mark".
Does this refer to each input set?
How do I detect the end of an input set?
My solution ends an input set trying to find a blank line but gets WA.

Thanks in advance for any help...

Ciao!!!

Claudio

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

Yes, the description is vague in this respect. I made the following assumptions:
1. The input set for each case ends either with a blank line or the EOF (there can be only one EOF, of course).
2. There are no blank lines within the input set for a case.

In other words: each case has one or more lines, each line containing one or more numbers. The last line of the last case may be terminated by an EOF, by NEWLINE+EOF, or even NEWLINE+NEWLINE+EOF, AFAIK.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard »

Hello.
I have a quastion.

Can there be spaces after the last number of the line???
Thanks.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa »

little joey wrote:Yes, the description is vague in this respect. I made the following assumptions:
1. The input set for each case ends either with a blank line or the EOF (there can be only one EOF, of course).
2. There are no blank lines within the input set for a case.

In other words: each case has one or more lines, each line containing one or more numbers. The last line of the last case may be terminated by an EOF, by NEWLINE+EOF, or even NEWLINE+NEWLINE+EOF, AFAIK.
Many thanks.
This confirmed that my assumptions were correct.
Actually my program was more tolerant and allowed non numeric characters between two newlines, so that a line with whitespace (I thought that tabs or spaces could be present) was considered blank.
My error was to underestimate the size of input. Just increasing the size of the input buffer helped to get accepted.

Thanks again!

Ciao!!!

Claudio

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa »

Eduard wrote:Can there be spaces after the last number of the line???
Thanks.
Actually I don't know if the Judge's input has redundant spaces, but my AC program tolerates them...

Ciao!!!

Claudio

wos
New poster
Posts: 8
Joined: Mon Jul 05, 2004 11:08 am

879 TLE

Post by wos »

Hi,

I am using BFS to transverse the graph, and then search for all those not visited and start the BFS on them again. I count how many times i found vertices that aren't visted, and that is the result. However using this algorithm i get TLE. So i was wondering if there is a faster algorithm to do this ?

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci »

Which is the largest value for N???

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci »

What is wrong with my code? I am getting Runtime Error :-?

Code: Select all

Cut after AC
Please help me!!!
Last edited by neno_uci on Sat Jun 25, 2005 6:30 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

neno_uci wrote:Which is the largest value for N???
Less than 1048576, that's for certain.

Your program gives wrong answers for the sample input in these forms:

Code: Select all

2

14  1 11 7 11 2 12 12 8 11 12 3 13 4 13 13 14
14  9 5 14 6 10

14
  1
11    7     11 2 12 12 8 11 12 3 13 4 13 13 14
14  9 5 14 6 10

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci »

Thanx to mf I solved the problem :D

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 879 - Circuit Nets

Post by DD »

wos wrote:Hi,

I am using BFS to transverse the graph, and then search for all those not visited and start the BFS on them again. I count how many times i found vertices that aren't visted, and that is the result. However using this algorithm i get TLE. So i was wondering if there is a faster algorithm to do this ?
I think you can try to use union-find disjoint set method, it would be mush faster. :D
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

sushil2006090
New poster
Posts: 7
Joined: Wed Feb 20, 2008 3:17 pm
Contact:

Re: 879 - Circuit Nets--RTE??

Post by sushil2006090 »

/*Sushil Kumar Singh */
#include <cassert>
#include <cctype>
#include <cfloat>
#include <cmath>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <valarray>
#include <vector>
#include <ext/numeric>
#include <ext/hash_map>
#include <ext/hash_set>
#include <ext/algorithm>

using namespace std;
using namespace __gnu_cxx;

#define pb push_back
#define vi vector<int>
#define vii vector<vi>
#define ii pair<int,int>
#define vs vector<string>
#define all(v) (v).begin(), (v).end()
#define For(i,x) for(int i=0;i<x;i++)
struct node
{
vector<int>adj;
};
bool flag[1048576];
vector<node>v(1048576);
int n;
void dfs(int nod)
{
flag[nod]=true;
for(int i=0;i<v[nod].adj.size();i++)
{
if(!flag[v[nod].adj])
{
dfs(v[nod].adj);
}
}
}
int main()
{
int test;
cin>>test;
string str;
bool mark=true;
while(test--)
{
v.clear();
int num1,num2;
cin>>n;
if(mark==true)
{
mark=false;
}
else
{
cout<<endl;
}
getline(cin,str);
memset(flag,false,sizeof(flag));
while(getline(cin,str))
{

if(str.size()==0) break;
stringstream ss(str);
while(ss>>num1>>num2)
{
v[num1].adj.push_back(num2);
v[num2].adj.push_back(num1);
}
}
int cn=0;
for(int i=1;i<=n;i++)
{
if(!flag)
{
dfs(i);
cn++;
}
}
cout<<cn<<endl;
}
system("pause");
}


donno y i am getting RTE for this code.. can ny1 help me out here??

Post Reply

Return to “Volume 8 (800-899)”