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 ){...}
col will equal Used[i1] and thereafter
thank you !
const 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...
}
}
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..).