Embedding a Tree (Challenge)

All submissions for this problem are available.
Read problem statements in Mandarin chinese and Vietnamese as well.
You are given a tree with N nodes. You should embed this tree in a 2D plane such that each node of the tree is located at a point with integer coordinates. Let's denote the coordinates of the ith node by p_{i} = (x_{i}, y_{i}). An edge between nodes u and v corresponds to a line segment between points p_{u} and p_{v}.
Formally, the mapping of the nodes to points should satisfy the following property: No two segments in the plane intersect each other. (However, it is allowed for two segments corresponding to edges with a common vertex to touch at the point which is mapped to this common vertex.) For example, assume that N = 4 and the tree is a path. Then the line segment connecting points p_{1} and p_{2} will touch the line segment connecting points p_{2} and p_{3} only at point p_{2}. However, the line segment connecting points p_{1} and p_{2} shouldn't intersect or touch the line segment connecting points p_{3} and p_{4}.
Additionally, there is a constraint on the length of each edge. For an edge (u, v), you are also given an integer L. You should ensure that the Euclidean distance between the points p_{u} and p_{v} is at least L.
Your objective is to find an embedding such that the sum of Euclidean distances between points corresponding to each pair of nodes (even if they aren't connected by an edge) is as low as possible.
Input
 The first line of the input contains a single integer N.
 The following N1 lines describe edges. The ith of these lines contains three spaceseparated integers u_{i}, v_{i} and L_{i}, which denote an edge between nodes u_{i} and v_{i} with length constraint L_{i}.
Output
Print N lines. For each valid i, the ith of these lines should contain two spaceseparated integers x_{i} and y_{i}.
For each node, these coordinates should be integers satisfying 10^{9} ≤ x_{i}, y_{i} ≤ 10^{9}. Additionally, no two nodes should be mapped to the same point.
Example
Input 5 1 2 3 2 3 4 2 4 6 3 5 5 Output 0 0 4 0 4 5 10 10 10 10
Explanation
Score
Your score will be the sum of pairwise Euclidean distances between the points corresponding to nodes.
For the above example, the score you obtain would be 110.976947161586110724.
Test Generation Process
There are four types of tests and three test cases for each type. During the contest, the displayed score will account for only one test case of each type, i.e. your program score is reflective of 33.333% (1/3) of the test files. However, if your program gets a nonAC verdict on any of the test files, your verdict will be nonAC. In other words, an AC verdict denotes that your program runs successfully on all the test files. After the end of the contest, your score will be changed to reflect the score over all of the test files.
In each test case:
 N = 1000
 for each edge, the parameter L is generated uniformly randomly between 1 and 5000
 1 ≤ u, v ≤ N
For the paragraph below, assume the function rnd.next(l, r) generates a random number uniformly in the range l through r (both inclusive).
Type 1:
K = 10; for i = 2 to N: if i <= K; parent[i] = 1 else: parent[i] = rnd.next(i  K, i  1)
Type 2:
K = 10 for i = 2 to N: parent[i] = rnd.next(1, min(i  1, K))
Type 3:
K = int(N / 3) = 333 for i = 2 to N: if i >= K and i <= N  K: parent[i] = i  1; else: if i < K: parent[i] = rnd.next(1, i  1) else: Parent[i] = rnd.next(N  K, i  1);
Type 4
Fix K = 25. Create K trees with N / K nodes each. for i = 2 to K: join the ith tree with rnd.next(1, i  1)th tree.
These two trees are joined by adding an edge between a randomly selected nodes from each tree.
Note that in all 4 types of tests, after running the above methods, the nodes are mapped to a random permutation of numbers {1, 2, ..., N}, which serve as new labels for the nodes; these labels are what is given as input. Therefore, the above mentioned methods won't generate the exact input trees, but the trees generated by them will be isomorphic to the actual input trees (so only the labels in the trees can change). Apart from this, the generation process is exactly as described above.
Author:  admin2 
Tags  admin2 
Date Added:  28022018 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions