It will be an open virtual contest — start whenever convenient

We'll try to keep things just as on IOI

You can use two pointers to achieve O(N)

no i am talking about the first problem, i wanted to know if the solution is o(n) time or o(nlogn) time

There is a download button in the upper right corner near "Jury messages" button. There you can find templates for different languages including C++.

I haven't coded this but i think it should get 100. Label the nodes 1..N on the main line and 1'...N' attached to them, x[i] be the distance from 1 to i and l[i] be the distance from i to i'. Bsearch the answer, suppose the answer is <= t. Let u[i] = l[i]-x[i], v[i] = l[i]+x[i]. Let x1 < x2 be the "x-coordinate" (analogous to x[i]s) that we will add the extra edge between. Then for any i<j with u[i]+v[j] > t we need to have |x[i]-x1| + |x[j]-x2| + c + l[i] + l[j] <= t. This can be expanded into 4 different ineqs.

(x1+x2) — x[i] — x[j] + l[i] + l[j] + c <= t (1)

(-x1-x2) + x[i] + x[j] + l[i] + l[j] + c <= t (2)

(x1-x2) — x[i] + x[j] + l[i] + l[j] + c <= t (3)

(-x1+x2) + x[i] — x[j] + l[i] + l[j] + c <= t (4)

Note that inequalities (1) and (2) can be considered for all pairs i,j with u[i]+v[j]>t (not necessarily just i<j) without changing the system. Also (3) is tightest when i', j' are the diameter of the original graph so that can be precompd outside the bsearch. With some O(nlgn) precomp we can calculate max(-x[i]-x[j]+l[i]+l[j]) and max(x[i]+x[j]+l[i]+l[j]) over all u[i]+v[j] > t in O(n). We now have the tightest inequalities on (1),(2),(3) and we can now iterate through x1 and keep the interval of valid (satisfying 1,2,3) x2's using two pointers. We take the x1,x2 with minimum -x1+x2 as if anything satisfies the (4) ineqs then so will this one. Then check this answer by calculating the diameter for the resultant graph (possible due to special form) in O(n) to implicitly check all the inequalities of form (4). O(nlgAns + nlgn) overall, perhaps there's a simpler soln though.