**Welcome to Codeforces Beta Round #25 (Div. 2)**

Authors of today's round problems are Mike Mirzayanov and me. I want to thank to Dmitry Levshunov for technical assistance in organizing the contest, as well as Gerald Agapov and Nikolay Kuznetsov for writing alternative solutions.

*I wish you all good luck!*

**UPD: **The contest is over, thank you to everyone for participating.

- Problems
- Standings
- Winner: marek.cygan

what sahould i do????????????????

i run this program correctly

I'm also very interested about this verdict.

Well, but why does my gcc-4.4.3 work with "%lld" just fine?

sorry for my bad English

them like if the shotest path go through according edge. So update cost for any query is O(N^2)

First, see if this new road is actually better than the shortest path from u to v. It may not be :)

Assuming it's an improvement, set a[u][v] = a[v][u] = d. Then, run Floyd-Warshall to update the shortest distances. Normally this would be O(n^3), but because only the distance between u and v changed, it suffices to use only u and v as midpoints, reducing the time to O(n^2). Given 300 roads, the total runtime is 300 * O(n^2) ~= 300^3 which is quite fine.

I got a PE for problem D!!!! Is there something wrong with the judge?

"=" means assignment, so your expression can be written this way:

col = Used[i1];

if (col ){...}

if (col = Used[i1]) { ... }

will equalcoland thereafterUsed[i1]not equal zerocolconst int N = 310;

int main() {

int n;

scanf("%d", &n);

int g[N][N];

for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++) {

scanf("%d", &g[i][j]);

assert(g[i][j] <= 1000); // runtime error...

}

}

such that from each city it is possible to get to any other city using these roads." i misunderstood the last part.Thanks

http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

Using KMP, it's easy to find for 2 given strings the longest suffix of the first one that is a prefix for the second one.

After that you simply try all posible permutations of the 3 strings given in the problem(watching for degenerate cases, when one of the strings is a substring of one of the other two..).

Thanks