| Submit | All submissions | Best solutions | Back to list |
MEPPERM - Maximum Edge of Powers of Permutation |
For a directed graph G where any vertex v has two weights Av and Bv, we call Au+Bv the weight of a edge (u,v). Let MaxEdge(G) be the maximum weight of the edges of G.
Given a permutation P on 1..n, we can derive a directed graph G=(V,E) where V={1,..,n} and (u,v) in E iff P(u)=v. Your task is to compute MaxEdge(Pk) for every k in 0..q-1.
Input
The first line contains a positive integer n.
The second line contains n integers in {1,..,n}, denoting the permutation P.
The third and the fourth line both contain n natural numbers, A1,..,An and B1,..,Bn respectively.
The fifth line contains a positive integer q.
Output
The only one line contains q integers MaxEdge(P0),..,MaxEdge(Pq-1), separated by a single space.
Example
Input:
3
3 2 1
0 1 2
2 2 0
5
Output:
3 4 3 4 3
Constraint
n <= 66000
Ai, Bi <= 16
q <= 106
Notice
The time limit is somehow strict. Please do not spoil the problem with a cheating solution.
Description updated on 2010-7-11
| Added by: | Lox |
| Date: | 2010-07-01 |
| Time limit: | 1s-3s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |
| Resource: | Own problem |
hide comments
|
2013-09-03 15:15:50 Tony Beta Lambda
That complexity being said, you need to optimize for a variety of cases to get it accepted. |
|
|
2010-08-20 20:50:11 Anton Lunyov
What meaning of natural numbers here? As I see from example zero is included. Do zeros appear in other tests? Re: Natural numbers include zeroes. Last edit: 2010-08-25 07:30:51 |
|
|
2011-06-06 08:49:25 Serge
Re: O(max{A_i,B_i}*nlogn) regardless of q Last edit: 2010-08-05 14:15:52 |
RSS