| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
Hey i was trying to solve King's Path on codeforces http://mirror.codeforces.com/problemset/problem/242/C but i am getting wrong answer on test 10; my code: http://mirror.codeforces.com/contest/242/submission/14186492
Can anyone point my mistake? Thanks.
Many of the solutions that i saw involved traversing the columns in a row to mark them elgible for being visited but this may time out if adequate tests are provided as their difference can be as large as 10^9
Auto comment: topic has been updated by javacoder1 (previous revision, new revision, compare).
BFS/DFS through matrix. But, since total number of fields is 10^5 it will clearly pass time. You don't need to traverse through whole matrix, mark rows and columns that you can visit (I used map). It will increase overall complexity, but it is more than enough.
You can check my code: http://mirror.codeforces.com/contest/242/submission/12684561
I tried to use dijkstra algorithm to figure the shortest path from source to end.I need someone to find a bug in my code so that it works.
Also your solution required iterating from start of a column to end but since no information is given about their difference we just can't iterate. Answer being less than 10^5 doesn't imply that the difference can't be as large as 10^9. Point me if i am wrong. this line: scanf ("%d%d%d", &red, &poc, &kraj); for (int i=poc;i<=kraj;i++) allow[make_pair(red, i)]++;
'Total length of all given segments doesn't exceed 10^5'. When we sum iterations of all these for loops, this sum cannot exceed 10^5, and that's the whole point.
the segments can be separated. e.g: 1 4 & 7 9. Your code will make all the cells between 1 and 8 allowed while 5 and 6 are not.
I think OP probably doesn't care anymore...