Цикл из 9999 ребер + одно рандомное ребро

It can be solved without hashing

I used hashing and got AC.

No :)

Well, main trick - it is not string problem :)

I used Suffix Arrays, Longest Common Prefix and Range Minimum Query to solve this problem.

Well, maybe my solution is not the most popular one. So I should better describe it.

cool

Well, if you look at standings you can easily understand that O(m*m) will definitely fail, since a lot of people have TLE. It can be solved faster. The main observation is that if the required edges exist then there is an odd cycle and all edges in answer belong to this cycle. So the first thing to do is to find some odd cycle with DFS. Then you can delete this cycle from graph. If the resulting graph is not biparate, then answer is zero. Otherwise you can run dfs from each of the nodes on cycle marking the colors of nodes. The goal is to understand which cycle nodes have the same color and which opposite. So, you will get some statements like "Nodes x and y of cycle have the same color" or "Nodes x and y of cycle have the opposite color". Obviously each statement is equivalent to statement "Edge to be removed is on segment [x,y] of cycle" or "Edge to be removed is on segment [y,x] of cycle" (depending on (y - x) % 2). Number of statements is linear because they are generated by DFS, so we have problem to find which cycle edges are on all generated segments of cycle, this problem can be solved by usual methods (sorting etc.). I don't know if this problem can be solved in a less complicated way, but even this solution can be coded on contest.
PS: sorry for my terrible english.

There is an O(n+m) solution based on DFS graph analysis.

написать разбор может только один человек, который все решил. 

Around lines 126-127... Shouldn't you be swapping v2 and v3 as well? You want to make sure all the data stays together. Every time you swap two teams, you'll want to swap team, v, v2, and v3.

A few notes... if you use a structure that has all of this data, you won't have to worry about only swapping parts of the data. Also, if you use a built-in sorting method, it'll run in O(n log n) rather than the O(n^2) sort you have here, and it'll take you less time to code.

"Let through" goals, i.e. the goals that your opponents scored in matches against you.

dp[m][s] = the minimal cost of a subset of items that you choose among the first m items so that the sum of (t_i+1) >= s (here i runs over the indices of the chosen items).
The answer is dp[n][n]

use printf("%I64d\n", ans);