COT - Count on a tree
You are given a tree with N nodes. The tree nodes are numbered from 1 to N. Each node has an integer weight.
We will ask you to perform the following operation:
- u v k : ask for the kth minimum weight on the path from node u to node v
In the first line there are two integers N and M. (N, M <= 100000)
In the second line there are N integers. The ith integer denotes the weight of the ith node.
In the next N-1 lines, each line contains two integers u v, which describes an edge (u, v).
In the next M lines, each line contains three integers u v k, which means an operation asking for the kth minimum weight on the path from node u to node v.
For each operation, print its result.
Input: 8 5 105 2 9 3 8 5 7 7 1 2 1 3 1 4 3 5 3 6 3 7 4 8
2 5 1
2 5 2
2 5 3
2 5 4
7 8 2
Guys who got accepted, what's your complexity? Mine is O((N+Q)logN) and it hardly passed with a lot of optimizations :)
Why have I been getting a RE result? It's well done on my computer. Can anyone give me some possible reasons?
don't use vector to store edges, or you will get TLE.
Alireza Ghorbanzadeh Neghab:
got accepted using only scanf() and printf().
I have got an Accepted!
@problemsetter, the fastest solution is double your time limit. Is it genuinely possible to do this problem in your given time limit with some algorithm?
get WA all the time.Last edit: 2013-04-25 07:24:25
|Cluster:||Cube (Intel G860)|
|Languages:||All except: ASM32-GCC ASM64 MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET|
|Resource:||Just for fun...|