10986 - Sending email

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

Moderator: Board moderators

blazej
New poster
Posts: 4
Joined: Mon Jan 23, 2006 5:01 pm

10986 - Sending email

Post by blazej » Mon Jan 23, 2006 5:08 pm

Can anyone tell me what can be the reason for getting whole the time TLE on this problem? I am using Dijskra's algorithm, and I don't think this problem can be solved faster...
Are there some "tricks" about reading the input?

I wiil be grateful for any help.

Renat
New poster
Posts: 10
Joined: Thu Jul 18, 2002 2:40 pm
Location: Russia
Contact:

Post by Renat » Mon Jan 23, 2006 5:17 pm

Do you use heap?

blazej
New poster
Posts: 4
Joined: Mon Jan 23, 2006 5:01 pm

Post by blazej » Mon Jan 23, 2006 5:21 pm

yes...
I've tried STL priority_queue, and as well mine heap...

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Mon Jan 23, 2006 5:59 pm

The input is quite large, so you should use scanf() instead of cin>> to read input.
If only I had as much free time as I did in college...

blazej
New poster
Posts: 4
Joined: Mon Jan 23, 2006 5:01 pm

Post by blazej » Mon Jan 23, 2006 6:10 pm

I'm using <cstdio>...

Renat
New poster
Posts: 10
Joined: Thu Jul 18, 2002 2:40 pm
Location: Russia
Contact:

Post by Renat » Mon Jan 23, 2006 7:05 pm

Then it's probably some error in your code. I've accepted this task with both STL and mine priority queues.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Mon Jan 23, 2006 7:28 pm

Are you stopping your dijkstra when you take node T out of the priority_queue? This does not improve the worst case complexity, but it improves the runtime on random test cases and can be quite an important optimization.

blazej
New poster
Posts: 4
Joined: Mon Jan 23, 2006 5:01 pm

Post by blazej » Mon Jan 23, 2006 7:49 pm

I finally got ACC. Renat was right, I couldn't find such a stupid bug...
So I'm sorry taking your time, but I have been working on this problem since saturday contest, so I decided to ask start this topic...
Adrian Kuegel - now my program doesn't do it, and it gets ACC at least :)

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Thu Jan 26, 2006 4:20 pm

Hi,

Please try this code on the judge:

Code: Select all

var f, p, c, n, m, s, t, i, j, k : longint;
begin
  readln(c);
  for p := 1 to c do begin
    readln(n, m, s, t);
    while m >= 50000 do write;
    for f := 1 to m do readln(i, j, k);
  end;
end.
This code gives TLE. That could mean that the test data is incorrect (may contain m >= 50000).

I might be wrong, but since I'm getting WA I'm trying everything I can think of...

Thanks for your attention.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Thu Jan 26, 2006 5:40 pm

Oops. A small mistake. There are test cases with m = 50000.
There are no test cases with m > 50000.
If only I had as much free time as I did in college...

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Thu Jan 26, 2006 7:28 pm

Hi,

Yes you are right. Changing >= into > would get rid of TLE (WA in < 1 sec.). And the same thing happens to n (n can be equal to 20000).

I have also tried this:

Code: Select all

var f, p, c, n, m, s, t, i, j, w : longint; 
begin 
  readln(c); 
  for p := 1 to c do begin 
    readln(n, m, s, t); 
    for f := 1 to m do begin
      readln(i, j, w); 
      while w > 10000 do write;
    end;
  end; 
end.
And this gives TLE as well, so... maybe we have some w > 10000?..... But since so many people have got this problem accepted (including PASCAL submissions) the mistake may be on my side...

Thanks again.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Ahmed_Hasan
New poster
Posts: 7
Joined: Sat Jul 09, 2005 7:58 pm

Getting TLE

Post by Ahmed_Hasan » Sun Jan 29, 2006 7:12 pm

I think there is nothing to do with the algorithm to make the solution faster. Because everybody talked here tried or solved it with dijkstra. But i m getting TLE for my dijkstra. So I m giving my dijkstra code here so that anybody can give me any hint to make my code faster.

Code: Select all


#include<cstdio>
#include<list>
#include<queue>
using namespace std;

#define maxv 20010
#define INF 999999999

struct node{int v,cost;};

list<node> G[maxv];	
int D[maxv];
int V,E,S,T;

//*************************Dijkstra*************************//
class Qele				//Q elements
{ 
	public: int v; 
	bool operator<(const Qele &t)const{	return D[t.v]<D[v];}
};
void Dijkstra(int s)
{
	int c1,v;
   Qele A[maxv];
	for(c1=0;c1<V;c1++) D[c1]=INF;
	for(c1=0;c1<V;c1++) A[c1].v=c1;
   D[s]=0;
	list<node>::iterator Adj;

	for(c1=0;c1<V;c1++){
		make_heap(A+c1,A+V);
		v=A[c1].v;
		if(v==T) break;
		for(Adj=G[v].begin();Adj!=G[v].end();Adj++)
			if( D[Adj->v]>D[v]+Adj->cost)
				D[Adj->v]=D[v]+Adj->cost;
    }
}
//*************************Dijkstra*************************//

void Init()
{
	int c1;
	for(c1=0;c1<=V;c1++)
	{
		G[c1].clear();
		D[c1]=INF;
	}

}

int main()
{
	freopen("10986.txt","r",stdin);
	int c1,cas,casc=0,v1,v2,cost;
	node n;
	scanf("%d",&cas);
	for(casc=1;casc<=cas;casc++)
	{
		Init();

		scanf("%d %d %d %d",&V,&E,&S,&T);
		for(c1=0;c1<E;c1++)
		{
			scanf("%d %d %d ",&v1,&v2,&cost);

			n.cost=cost;
			n.v=v2;
			G[v1].push_back(n);
			n.v=v1;
			G[v2].push_back(n);
		}

		Dijkstra(S);
		if(D[T]==INF)
			printf("Case #%d: unreachable\n",casc);
		else
			printf("Case #%d: %d\n",casc,D[T]);

	}
	return 0;
}
Last edited by Ahmed_Hasan on Sun Jan 29, 2006 8:02 pm, edited 1 time in total.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sun Jan 29, 2006 7:33 pm

Your algorithm runs in n^2 time. In your Dijkstra() function, for each vertex, you run make_heap().

make_heap() takes linear time.
If only I had as much free time as I did in college...

Ahmed_Hasan
New poster
Posts: 7
Joined: Sat Jul 09, 2005 7:58 pm

Post by Ahmed_Hasan » Sun Jan 29, 2006 10:29 pm

Thanks Abednego. It was really an important information about the make_heap(). I think STL should not be like this, it should work in the best way. Whatever, now I use priority Q and got AC.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sun Jan 29, 2006 10:36 pm

How could you possibly write make_heap() so that it would run in faster than linear time?! make_heap() _creates_ a heap. it doesn't modify an existing heap. To create a heap, you have to read the whole given array, and that takes linear time.
If only I had as much free time as I did in college...

Post Reply

Return to “Volume 109 (10900-10999)”