Make difference array, where dif[i] = i - a[i]

Try
7 10
1 2
1 3
1 4
5 6
5 7
8 9
8 10
8 11
12 13
12 14
This test changed my solution totally. Hope it helps you:)

Can the mouse go under the furniture? I mean, can it's way cross the polygons?

Actually, you can solve it as a graph problem, where numbers 0, 1, ..., n are vertices, which connected like: 0-1, 1-2, ...

I was able to solve it just by computing matrix determinant. Nothing to do with graphs, just taking advantage of matrix sparsity.

WA #3: 1 1 -> 2
WA #5: 2 1 -> 3
WA #7: 5 3 -> 29
WA #8: 6 5 -> 63
WA #9: 5 1 -> 13

This is the case of a particularly small competition!

If the starting point A is a station but you go by feet, is the station a visited station. For example, what is the solution for the following:
100 101
3
0 0
0 10
1 0
1 2
2 3
0 0
0 0
1 0

If you have TL on test 21, 49 or 50 you should use gets. I get AC with 0.3 s.

3 4
0 2000 1000 3000 0 3000
0 0 3000 0 3000 3000 0 3000
ans: 647.1067811865

5 6
0 2000 500 2500 1000 3000 1500 3000 0 3000
0 0 1500 0 3000 0 1500 0 3000 3000 0 3000
ans: 647.1067811865

3 4
0 0 4000 0 2000 4000
0 0 4000 0 4000 4000 0 4000
ans: 3517.7087639997

4 4
0 0 3000 0 3000 3000 0 3000
2000 2000 5000 2000 5000 5000 2000 5000
ans: 940

4 4
0 0 3000 0 3000 3000 0 3000
1000 1000 -2000 1000 -2000 -2000 1000 -2000
ans: 940

4 3
0 0 30000 0 30000 30000 0 30000
10000 40000 40000 10000 40000 40000
ans: 7011.0678118655

4 4
0 0 3000 0 3000 3000 0 3000
-1000 1000 5000 1000 5000 2000 -1000 2000
ans: 1940

4 4
0 0 3000 0 3000 3000 0 3000
-1000 2000 1000 -1000 2000 -1000 -1000 2000
ans: 647.1067811865

3 3
0 0 4000 2000 0 4000
3000 2000 7000 0 7000 4000
ans: 387.2135955000

Also, WA6 = integer overflow

Can you give me any hint or any tests?

Thanks in advance.

Well, here are some hints:
1. Use DFA. If you do'nt know what it is, visit this page http://en.wikipedia.org/wiki/Deterministic_finite_automaton (pay attention to the table of states)

2. use getc() instead of cin>>ch or cin.getch() or whatever you use (for C++/C only)

3. Try this:
3
outputoutputinputon

inputone

Edited by author 13.06.2007 17:36

I have WA on test 7. What i need to do?

Output is EndPoint. EndPoint is simple.

4 3
1 1 1
2 2 2
3 3 3
4 4 4

> 0

my solution is: edge number + component number - 1.

Use long long

What is test 5? I can give my code(It's not working), runtime error(access violation)

Any tips?

you can use Binary Lifting,find lca of u and v
you find distance u with root of tree
the result=dis[a]+dis[b]-2*dis[lca(a,b)]

No clue as to what's wrong. Can anyone please give me a hint or what's the case?