I seemed to cheat my way into the problem by simply randomly printing n/2 numbers between 1 to n and i recieved 63 points…
how was the problem supposed to be solved…
did anyone else solve the problem in similar way?
BTW, your final score may be very far from 63 points (and I am not even sure in which side it will change :D). While we have N<=1e6 in problem statement, actually n<=100 in all tests scored by pretest evaluation 
And it is not a cheating, it is a good way of solving approximate task)
I didn’t spend much time on solving this problem, and my approach was quite straightforward idea - write some sort of MST algorithm, but adding furthest point every time (one with largest total weight of edges between it and MST); do it “almost” n/2 times, but for last points use different penalty function - how answer will change if we’ll take this point (so now not only edges between this point and MST matter, but also all other edges from this point).
It gives ~94 points on pretests.
Reduced to 48 points now !!! 