TAXI2 - Theater shade in Berland


In Berland a new movie was released on the occassion of 14th Feb. The craze for this movie was very much among the peoples of the city. So many of them decided to go to the only Movie Theatre of Berland. As berland is very much developed there are many large(tall) buildings, including the movie theatre. At each building except theatre, there exist a person (who wants to see movie) or a taxi driver with his taxi. As it is very late in the night each taxi driver will only accomodate only one passenger and also he will only drive for T[i] HRS (return journey is not included). You will be given the distance between building D[i] and the speed of each taxi driver S[i]. As I am the owner of this theatre help me by telling, the maximum number of people I will see in the theatre for the movie. N+P+1th building is the my theatre. Also, if a taxi starts his journey by taking a passenger, it only stops at the theatre.

Input

  • First line contains TT the number of test cases.
  • First line of each test test case contains N, P and R denoting the number of taxi, number of people, and the number of roads between buildings.
  • Next line contains N space-seperated integers representing the building where taxi is present.
  • Next line contains P space-seperated integers representing the building where passengers is present.
  • Next R lines contains X, Y, and D[i] the building connected via road and the distance between them in KMs.
  • Next line contains N space-sperated integers S[i] giving the speed details of each taxi in KM/HRs.
  • Next line contains N space-sperated integers T[i] giving the time details of each taxi in HRs.

Output

  • Maximum number of people that will visit my theatre.

Constraints 

  • 1 <= TT <= 5
  • 1 <= N <= 500
  • 1 <= P <= 1000
  • 1 <= R <= 50000
  • 1 <= X, Y <= N
  • 5 <= S[i] <= 50
  • 1 <= T[i] <= 5
  • 1 <= D[i] <= 100

Example

Input:
1
1 2 4
2
1 3
1 2 5
2 3 5
3 4 10
1 3 8
20
1

Output:
1

hide comments
Oleg: 2023-08-16 16:34:50

Problem is actually legit and pretty unique.
Only clarification required: Each taxy is willing to serve only 1 passenger and willing to drive from own home to home of passenger + from passenger home to theater if that distance <= S * T for that taxi.

Sigma Kappa: 2017-07-29 21:18:04

Yes, I second @weathervane. I also hate problems with such details unclear.

weathervane: 2016-11-17 19:37:53

There is too much irrelevant waffle about height and shade, and too many loose ends in the problem statement to make it worth investing the time trying to solve it. Do taxis return to base before picking up another customer? Is the time from taxi base to pickup reckoned? Also the suspicious condition 1 <= X, Y <= N which I suspect should be 1 <= X, Y <= (N+P+1) . Hence its unpopularity.

Last edit: 2016-11-17 19:53:02
VilimL: 2016-06-30 21:50:37

O(sqrt(N+P) N P + N R log R) gives TLE and I don't see what kind of ridiculous optimizations I should use...

[Rampage] Blue.Mary: 2016-03-19 05:19:48

I wonder the time factor for this problem. You have a standard program that run in at most 0.5 second? Time limit should be (at least) 2.5 ~ 3 * judges' slowest solution.

Edit: I get AC by some ridiculous optimizations on a program with time complexity O(N(N+P)R+(N+P)^3) (which is almost 4*10^10)!!!

Last edit: 2016-03-19 06:05:59

Added by:adi28galaxyak
Date:2016-03-18
Time limit:1s-1.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:own