| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 16105 |
2015-08-16T04:20:26 Z |
gs14004 |
Wombats (IOI13_wombats) |
C++14 |
|
7343 ms |
191616 KB |
#include "wombats.h"
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
struct node{
int adj[205][205];
};
int a[5000][200], b[5000][200];
int n, m;
int opt[205][205];
node merge(node& a, node& b){
node c;
memset(c.adj,0x3f,sizeof(c.adj));
// opt(i-1, j) <= opt(i,j) <= opt(i,j+1)
for(int i=0; i<m; i++){
for(int j=0; j<m; j++){
if(c.adj[0][i] > a.adj[0][j] + b.adj[j][i]){
c.adj[0][i] = a.adj[0][j] + b.adj[j][i];
opt[0][i] = j;
}
}
}
for(int i=1; i<m; i++){
opt[i][m] = m-1;
for(int j=m-1; j>=0; j--){
for(int k=opt[i-1][j]; k<=opt[i][j+1]; k++){
if(c.adj[i][j] > a.adj[i][k] + b.adj[k][j]){
c.adj[i][j] = a.adj[i][k] + b.adj[k][j];
opt[i][j] = k;
}
}
}
}
return c;
}
node tmp[11];
struct seg{
node tree[1050];
void remake(int s, int e, int p){
for(int i=s; i<=e; i++){
for(int j=0; j<m; j++){
for(int k=0; k<m; k++){
tmp[i-s].adj[j][k] = b[i][k] + abs((j ? a[i][j-1] : 0) - (k ? a[i][k-1] : 0));
}
}
}
tree[p] = tmp[0];
for(int i=1; i<=e-s; i++){
tree[p] = merge(tree[p], tmp[i]);
}
}
void add(int pos, int ps, int pe, int p){
if(pe - ps <= 10){
remake(ps, pe, p);
return;
}
int pm = (ps + pe) / 2;
if(pos <= pm) add(pos, ps, pm, 2*p);
else add(pos, pm+1, pe, 2*p+1);
tree[p] = merge(tree[2*p], tree[2*p+1]);
}
void init(int ps, int pe, int p){
if(pe - ps <= 10){
remake(ps, pe, p);
return;
}
int pm = (ps + pe) / 2;
init(ps, pm, 2*p);
init(pm+1, pe, 2*p+1);
tree[p] = merge(tree[2*p], tree[2*p+1]);
}
}seg;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
n = R, m = C;
for(int i=0; i<R; i++){
for(int j=0; j<C; j++){
a[i][j] = H[i][j] + (j ? a[i][j-1] : 0);
b[i][j] = V[i][j];
}
}
seg.init(0,n-1,1);
}
void changeH(int P, int Q, int W) {
int diff = W - (a[P][Q] - (Q ? a[P][Q-1] : 0));
for(int i=Q; i<m; i++){
a[P][i] += diff;
}
seg.add(P,0,n-1,1);
}
void changeV(int P, int Q, int W) {
b[P][Q] = W;
seg.add(P,0,n-1,1);
}
int escape(int V1, int V2) {
return seg.tree[1].adj[V1][V2];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
402 ms |
191444 KB |
Output is correct - 505 tokens |
| 2 |
Correct |
419 ms |
191448 KB |
Output is correct - 505 tokens |
| 3 |
Correct |
483 ms |
191452 KB |
Output is correct - 200005 tokens |
| 4 |
Correct |
397 ms |
191452 KB |
Output is correct - 505 tokens |
| 5 |
Correct |
374 ms |
191444 KB |
Output is correct - 505 tokens |
| 6 |
Correct |
0 ms |
191120 KB |
Output is correct - 6 tokens |
| 7 |
Correct |
0 ms |
191116 KB |
Output is correct - 6 tokens |
| 8 |
Correct |
0 ms |
191116 KB |
Output is correct - 6 tokens |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
191116 KB |
Output is correct - 6 tokens |
| 2 |
Correct |
0 ms |
191124 KB |
Output is correct - 6 tokens |
| 3 |
Correct |
0 ms |
191116 KB |
Output is correct - 6 tokens |
| 4 |
Correct |
0 ms |
191120 KB |
Output is correct - 405 tokens |
| 5 |
Correct |
0 ms |
191116 KB |
Output is correct - 405 tokens |
| 6 |
Correct |
0 ms |
191124 KB |
Output is correct - 405 tokens |
| 7 |
Correct |
0 ms |
191120 KB |
Output is correct - 405 tokens |
| 8 |
Correct |
0 ms |
191116 KB |
Output is correct - 366 tokens |
| 9 |
Correct |
0 ms |
191120 KB |
Output is correct - 405 tokens |
| 10 |
Correct |
3 ms |
191120 KB |
Output is correct - 366 tokens |
| 11 |
Correct |
88 ms |
191116 KB |
Output is correct - 200005 tokens |
| 12 |
Correct |
0 ms |
191120 KB |
Output is correct - 405 tokens |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
166 ms |
191284 KB |
Output is correct - 105 tokens |
| 2 |
Correct |
137 ms |
191280 KB |
Output is correct - 105 tokens |
| 3 |
Correct |
173 ms |
191288 KB |
Output is correct - 105 tokens |
| 4 |
Correct |
167 ms |
191284 KB |
Output is correct - 105 tokens |
| 5 |
Correct |
177 ms |
191284 KB |
Output is correct - 105 tokens |
| 6 |
Correct |
0 ms |
191120 KB |
Output is correct - 6 tokens |
| 7 |
Correct |
0 ms |
191120 KB |
Output is correct - 6 tokens |
| 8 |
Correct |
0 ms |
191116 KB |
Output is correct - 6 tokens |
| 9 |
Correct |
594 ms |
191280 KB |
Output is correct - 105 tokens |
| 10 |
Correct |
0 ms |
191120 KB |
Output is correct - 8 tokens |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
397 ms |
191452 KB |
Output is correct - 1005 tokens |
| 2 |
Correct |
378 ms |
191448 KB |
Output is correct - 1005 tokens |
| 3 |
Correct |
404 ms |
191616 KB |
Output is correct - 1005 tokens |
| 4 |
Correct |
446 ms |
191444 KB |
Output is correct - 100005 tokens |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
160 ms |
191284 KB |
Output is correct - 105 tokens |
| 2 |
Correct |
139 ms |
191284 KB |
Output is correct - 105 tokens |
| 3 |
Correct |
167 ms |
191284 KB |
Output is correct - 105 tokens |
| 4 |
Correct |
170 ms |
191280 KB |
Output is correct - 105 tokens |
| 5 |
Correct |
164 ms |
191280 KB |
Output is correct - 105 tokens |
| 6 |
Correct |
393 ms |
191452 KB |
Output is correct - 1005 tokens |
| 7 |
Correct |
389 ms |
191452 KB |
Output is correct - 1005 tokens |
| 8 |
Correct |
421 ms |
191616 KB |
Output is correct - 1005 tokens |
| 9 |
Correct |
440 ms |
191448 KB |
Output is correct - 100005 tokens |
| 10 |
Correct |
395 ms |
191444 KB |
Output is correct - 505 tokens |
| 11 |
Correct |
376 ms |
191444 KB |
Output is correct - 505 tokens |
| 12 |
Correct |
484 ms |
191452 KB |
Output is correct - 200005 tokens |
| 13 |
Correct |
389 ms |
191448 KB |
Output is correct - 505 tokens |
| 14 |
Correct |
389 ms |
191448 KB |
Output is correct - 505 tokens |
| 15 |
Correct |
0 ms |
191124 KB |
Output is correct - 6 tokens |
| 16 |
Correct |
0 ms |
191120 KB |
Output is correct - 6 tokens |
| 17 |
Correct |
0 ms |
191116 KB |
Output is correct - 6 tokens |
| 18 |
Correct |
3 ms |
191120 KB |
Output is correct - 405 tokens |
| 19 |
Correct |
0 ms |
191120 KB |
Output is correct - 405 tokens |
| 20 |
Correct |
0 ms |
191116 KB |
Output is correct - 405 tokens |
| 21 |
Correct |
0 ms |
191124 KB |
Output is correct - 405 tokens |
| 22 |
Correct |
0 ms |
191120 KB |
Output is correct - 366 tokens |
| 23 |
Correct |
0 ms |
191120 KB |
Output is correct - 405 tokens |
| 24 |
Correct |
0 ms |
191120 KB |
Output is correct - 366 tokens |
| 25 |
Correct |
93 ms |
191120 KB |
Output is correct - 200005 tokens |
| 26 |
Correct |
0 ms |
191116 KB |
Output is correct - 405 tokens |
| 27 |
Correct |
590 ms |
191280 KB |
Output is correct - 105 tokens |
| 28 |
Correct |
1911 ms |
191452 KB |
Output is correct - 50005 tokens |
| 29 |
Correct |
2056 ms |
191444 KB |
Output is correct - 50005 tokens |
| 30 |
Correct |
2061 ms |
191444 KB |
Output is correct - 50005 tokens |
| 31 |
Correct |
2040 ms |
191448 KB |
Output is correct - 200005 tokens |
| 32 |
Correct |
0 ms |
191120 KB |
Output is correct - 8 tokens |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
163 ms |
191284 KB |
Output is correct - 105 tokens |
| 2 |
Correct |
133 ms |
191284 KB |
Output is correct - 105 tokens |
| 3 |
Correct |
168 ms |
191288 KB |
Output is correct - 105 tokens |
| 4 |
Correct |
174 ms |
191284 KB |
Output is correct - 105 tokens |
| 5 |
Correct |
160 ms |
191284 KB |
Output is correct - 105 tokens |
| 6 |
Correct |
366 ms |
191444 KB |
Output is correct - 1005 tokens |
| 7 |
Correct |
396 ms |
191448 KB |
Output is correct - 1005 tokens |
| 8 |
Correct |
407 ms |
191608 KB |
Output is correct - 1005 tokens |
| 9 |
Correct |
440 ms |
191448 KB |
Output is correct - 100005 tokens |
| 10 |
Correct |
383 ms |
191448 KB |
Output is correct - 505 tokens |
| 11 |
Correct |
381 ms |
191452 KB |
Output is correct - 505 tokens |
| 12 |
Correct |
461 ms |
191448 KB |
Output is correct - 200005 tokens |
| 13 |
Correct |
389 ms |
191448 KB |
Output is correct - 505 tokens |
| 14 |
Correct |
374 ms |
191444 KB |
Output is correct - 505 tokens |
| 15 |
Correct |
2950 ms |
191452 KB |
Output is correct - 11 tokens |
| 16 |
Correct |
7343 ms |
191616 KB |
Output is correct - 200005 tokens |
| 17 |
Correct |
0 ms |
191120 KB |
Output is correct - 6 tokens |
| 18 |
Correct |
0 ms |
191120 KB |
Output is correct - 6 tokens |
| 19 |
Correct |
0 ms |
191124 KB |
Output is correct - 6 tokens |
| 20 |
Correct |
3 ms |
191120 KB |
Output is correct - 405 tokens |
| 21 |
Correct |
0 ms |
191120 KB |
Output is correct - 405 tokens |
| 22 |
Correct |
0 ms |
191116 KB |
Output is correct - 405 tokens |
| 23 |
Correct |
0 ms |
191120 KB |
Output is correct - 405 tokens |
| 24 |
Correct |
0 ms |
191116 KB |
Output is correct - 366 tokens |
| 25 |
Correct |
0 ms |
191120 KB |
Output is correct - 405 tokens |
| 26 |
Correct |
0 ms |
191116 KB |
Output is correct - 366 tokens |
| 27 |
Correct |
90 ms |
191116 KB |
Output is correct - 200005 tokens |
| 28 |
Correct |
0 ms |
191116 KB |
Output is correct - 405 tokens |
| 29 |
Correct |
602 ms |
191280 KB |
Output is correct - 105 tokens |
| 30 |
Correct |
1942 ms |
191448 KB |
Output is correct - 50005 tokens |
| 31 |
Correct |
5980 ms |
191448 KB |
Output is correct - 100005 tokens |
| 32 |
Correct |
6016 ms |
191452 KB |
Output is correct - 100005 tokens |
| 33 |
Correct |
2031 ms |
191448 KB |
Output is correct - 50005 tokens |
| 34 |
Correct |
6386 ms |
191448 KB |
Output is correct - 100005 tokens |
| 35 |
Correct |
2038 ms |
191444 KB |
Output is correct - 50005 tokens |
| 36 |
Correct |
6503 ms |
191448 KB |
Output is correct - 100005 tokens |
| 37 |
Correct |
2015 ms |
191448 KB |
Output is correct - 200005 tokens |
| 38 |
Correct |
6433 ms |
191612 KB |
Output is correct - 200005 tokens |
| 39 |
Correct |
0 ms |
191120 KB |
Output is correct - 8 tokens |
| 40 |
Correct |
6692 ms |
191452 KB |
Output is correct - 100005 tokens |
