:)

Ok, USACO's answer: "Wifi setup: If the answer is an integer, print it as an integer. If it is half-integral (a decimal ending with .5), print it as a decimal with one digit after the decimal point."

4 hours.

Solutions are checked only on the sample test cases during the contest . They will be evaluated later and you will know your results only when they officially declared.

As far as I understand, "starting window" will end at this time, however it's possible to start the contest at this time so we can only discuss tasks 4 hours later.

I originally understood it that way so I think it could. :) Here's a sketch of an O(n log^2 n) solution: First, let's find the center of the tree C and root the tree at C. Find the list of lengths from C to every other vertex and sort it. Now, for each element a of the list we can easily compute number of other elements b, such that a + b <= L. That way, we are able to find for each vertex v the number of vertices w s.t. the path v-->C-->w is of length <= L. Doing roughly the same thing for length lists limited to every single subtree of C, we can subtract for each vertex v the number of vertices w such that the shortest path from v to w does not go through C. Overally, for each vertex we will know the number of vertices located past vertex C, that are still close enough to be counted. Now all you need to do is to delete edges adjacent to C and recurse on each subtree. Every subtree is at least two times smaller, so the complexity is O(n log^2 n).

Any idea how to do that in O(n log n)? :)

Draw field after coordinate compression, next bfs. May be it's not optimal solution.

Is there a way how to see the problems of the other divisions, except of waiting some days? :)

You may also try this problem, http://uva.onlinejudge.org/external/119/11918.html, It also requires grid compression, a bit harder than the usaco's one.

If you need first lexicographically, you always try to set first element of the sequence the least, that there exist answer starting with this element.

I did this way. Matching exists if and only if for every group it's not larger than sum of the other groups. So main idea is to choose two elements least lexicographically, and try them put in the first place and check whether you can continue.

There are several different situations, so you must be accurate when solving them.

I'm not sure I see how to use bipartite matching to solve this. Care to explain?

I intended for it to be solved greedily.

I was about to post that:)

They should put more informations on the website about the true status of the contest :/

State: denotes the length of the shortest path to vertex v with capacity . Compress the capacities in the given input into at most M ranks. Then it suffices to solve the problem using Dijkstra.

I used a modified Dijkstra but I have a doubt if that problem can be solved by network flow.

I solved it by DP.

My approach was Binary search[ on minimum capacity ] + Dijkstra

Well my solution was:

• Dijkstra returning L for any given lower bound on C (edges with capacity < C are cut off from the graph)

• the return value of this is non-increasing for increasing C

• since we're only interested in integer results, it's sufficient to consider only such C, for which (integer division) X/C isn't equal X/(C+1), because if they are equal, then the solution for X/C is obviously better

• EDIT: for C \ge \sqrt(X), X/C \le \sqrt(X), so there are O(\sqrt(X)) interesting C, and time complexity is therefore O(\sqrt(X)M\lg(N))... not optimal, but hopefully sufficient, haha

SILVER-WIFI_SETUP : I thought that cout << res; will print what was expected. But it prints 1.65947e+06 instead of 1659471. So I lost points of test2,test3,test7. Replaced it with :

printf("%d",(int)res);
if (res != (int)res) printf(".5");

and got full points.

No, it's impossible, even if your result is 0.