| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 2481 |
2013-07-22T12:08:49 Z |
kriii |
Wombats (IOI13_wombats) |
C++ |
|
4124 ms |
26672 KB |
#include "wombats.h"
#define group_size 500
const int NON = 0x7fffffff;
int N, M, G, Start[30], End[30], Z = 32;
int ANS[200][200],GO[64][200][200],OUT[64],NOW[200],LEFT[200],RIGHT[200];
int HH[5000][200],VV[5000][200];
inline int min(int a, int b){return a < b ? a : b;}
void going(int i)
{
int j;
for (j=0;j<M;j++) LEFT[j] = RIGHT[j] = NOW[j];
for (j=1;j<M;j++){
if (LEFT[j-1] == NON) continue;
LEFT[j] = min(LEFT[j],LEFT[j-1]+HH[i][j-1]);
}
for (j=M-2;j>=0;j--){
if (RIGHT[j+1] == NON) continue;
RIGHT[j] = min(RIGHT[j],RIGHT[j+1]+HH[i][j]);
}
for (j=0;j<M;j++){
NOW[j] = min(NOW[j],LEFT[j]);
NOW[j] = min(NOW[j],RIGHT[j]);
}
}
void make()
{
int i,j;
for (i=0;i<M;i++){
for (j=0;j<M;j++) NOW[j] = GO[1][i][j];
going(N-1);
for (j=0;j<M;j++) ANS[i][j] = NOW[j];
}
}
void modify(int g)
{
int i,j,k,x=g+Z,s;
for (i=0;i<M;i++){
for (j=0;j<M;j++) NOW[j] = NON;
NOW[i] = 0;
for (k=Start[g];k<End[g];k++){
going(k);
for (j=0;j<M;j++) NOW[j] += VV[k][j];
}
for (j=0;j<M;j++) GO[x][i][j] = NOW[j];
}
x /= 2; s = 1;
while (x){
if (OUT[x*2] > 0 || (OUT[x*2] == 0 && OUT[x*2+1] == s)) for (i=0;i<M;i++) for (j=0;j<M;j++) GO[x][i][j] = GO[x*2][i][j];
else{
for (i=0;i<M;i++) for (j=0;j<M;j++) GO[x][i][j] = NON;
for (i=0;i<M;i++) for (j=0;j<M;j++) for (k=0;k<M;k++) GO[x][i][j] = min(GO[x][i][j],GO[x*2][i][k]+GO[x*2+1][k][j]);
}
x /= 2; s *= 2;
}
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
N = R; M = C;
G = (R + group_size - 1) / group_size; int i,j;
for (i=0;i<G;i++){
Start[i] = i * group_size;
End[i] = (i + 1) * group_size;
}
if (End[G-1] >= R) End[G-1] = R-1;
if (Start[G-1] == End[G-1]) G--;
for (i=0;i<R;i++) for (j=0;j<C-1;j++) HH[i][j] = H[i][j];
for (i=0;i<R-1;i++) for (j=0;j<C;j++) VV[i][j] = V[i][j];
for (i=G;i<Z;i++) OUT[i+Z] = 1;
for (i=Z-1;i>=1;i--) OUT[i] = OUT[i*2] + OUT[i*2+1];
for (i=0;i<G;i++) modify(i);
}
void changeH(int P, int Q, int W) {
HH[P][Q] = W;
modify(P/group_size);
make();
}
void changeV(int P, int Q, int W) {
VV[P][Q] = W;
modify(P/group_size);
make();
}
int escape(int V1, int V2) {
return ANS[V1][V2];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
26672 KB |
Output is correct |
| 2 |
Correct |
4 ms |
26672 KB |
Output is correct |
| 3 |
Correct |
101 ms |
26672 KB |
Output is correct |
| 4 |
Correct |
8 ms |
26672 KB |
Output is correct |
| 5 |
Correct |
5 ms |
26672 KB |
Output is correct |
| 6 |
Correct |
0 ms |
26672 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
26672 KB |
Output isn't correct - 정답과 다른 결과를 출력하여 중간에 강제종료되었습니다. |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
26672 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
26672 KB |
Output isn't correct - 정답과 다른 결과를 출력하여 중간에 강제종료되었습니다. |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1402 ms |
26672 KB |
Output is correct |
| 2 |
Correct |
1386 ms |
26672 KB |
Output is correct |
| 3 |
Correct |
1648 ms |
26672 KB |
Output is correct |
| 4 |
Correct |
1415 ms |
26672 KB |
Output is correct |
| 5 |
Correct |
1390 ms |
26672 KB |
Output is correct |
| 6 |
Correct |
0 ms |
26672 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
26672 KB |
Output isn't correct - 정답과 다른 결과를 출력하여 중간에 강제종료되었습니다. |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
26672 KB |
Output is correct |
| 2 |
Correct |
12 ms |
26672 KB |
Output is correct |
| 3 |
Correct |
16 ms |
26672 KB |
Output is correct |
| 4 |
Correct |
71 ms |
26672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1407 ms |
26672 KB |
Output is correct |
| 2 |
Correct |
1381 ms |
26672 KB |
Output is correct |
| 3 |
Correct |
1640 ms |
26672 KB |
Output is correct |
| 4 |
Correct |
1684 ms |
26672 KB |
Output is correct |
| 5 |
Correct |
1626 ms |
26672 KB |
Output is correct |
| 6 |
Correct |
17 ms |
26672 KB |
Output is correct |
| 7 |
Correct |
16 ms |
26672 KB |
Output is correct |
| 8 |
Correct |
17 ms |
26672 KB |
Output is correct |
| 9 |
Correct |
60 ms |
26672 KB |
Output is correct |
| 10 |
Correct |
3 ms |
26672 KB |
Output is correct |
| 11 |
Correct |
3 ms |
26672 KB |
Output is correct |
| 12 |
Correct |
85 ms |
26672 KB |
Output is correct |
| 13 |
Correct |
6 ms |
26672 KB |
Output is correct |
| 14 |
Correct |
5 ms |
26672 KB |
Output is correct |
| 15 |
Correct |
0 ms |
26672 KB |
Output is correct |
| 16 |
Incorrect |
0 ms |
26672 KB |
Output isn't correct - 정답과 다른 결과를 출력하여 중간에 강제종료되었습니다. |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1406 ms |
26672 KB |
Output is correct |
| 2 |
Correct |
1616 ms |
26672 KB |
Output is correct |
| 3 |
Correct |
1669 ms |
26672 KB |
Output is correct |
| 4 |
Correct |
1422 ms |
26672 KB |
Output is correct |
| 5 |
Correct |
1387 ms |
26672 KB |
Output is correct |
| 6 |
Correct |
15 ms |
26672 KB |
Output is correct |
| 7 |
Correct |
14 ms |
26672 KB |
Output is correct |
| 8 |
Correct |
14 ms |
26672 KB |
Output is correct |
| 9 |
Correct |
59 ms |
26672 KB |
Output is correct |
| 10 |
Correct |
5 ms |
26672 KB |
Output is correct |
| 11 |
Correct |
6 ms |
26672 KB |
Output is correct |
| 12 |
Correct |
85 ms |
26672 KB |
Output is correct |
| 13 |
Correct |
4 ms |
26672 KB |
Output is correct |
| 14 |
Correct |
3 ms |
26672 KB |
Output is correct |
| 15 |
Incorrect |
4124 ms |
26672 KB |
Output isn't correct - 정답과 다른 결과를 출력하여 중간에 강제종료되었습니다. |
| 16 |
Halted |
0 ms |
0 KB |
- |
