#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXR = 5000;
const int MAXC = 200;
const int INF = 987654321;
int R, C, H[MAXR+10][MAXC+10], V[MAXR+10][MAXC+10];
struct Node
{
vector<vector<int>> V;
Node() { V=vector<vector<int>>(C, vector<int>(C)); }
};
Node tree[MAXR*4+10];
void add(Node &now, Node &lc, Node &rc, int pos)
{
int i, j, k;
now=Node();
for(i=0; i<C; i++)
{
for(j=0; j<C; j++)
{
int t=INF;
for(k=0; k<C; k++) t=min(t, lc.V[i][k]+rc.V[k][j]+V[pos][k]);
now.V[i][j]=t;
}
}
}
void init(int node, int tl, int tr)
{
if(tl==tr)
{
int i, j;
tree[node]=Node();
for(i=0; i<C; i++)
{
int s=0;
for(j=i+1; j<C; j++)
{
s+=H[tl][j-1];
tree[node].V[i][j]=tree[node].V[j][i]=s;
}
}
return;
}
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
add(tree[node], tree[node*2], tree[node*2+1], mid);
}
void init(int _R, int _C, int _H[5000][200], int _V[5000][200])
{
int i, j;
R=_R; C=_C;
for(i=0; i<R; i++) for(j=0; j+1<C; j++) H[i][j]=_H[i][j];
for(i=0; i+1<R; i++) for(j=0; j<C; j++) V[i][j]=_V[i][j];
init(1, 0, R-1);
}
void updateH(int node, int tl, int tr, int y)
{
if(tl==tr)
{
int i, j;
for(i=0; i<C; i++)
{
int s=0;
for(j=i+1; j<C; j++)
{
s+=H[tl][j-1];
tree[node].V[i][j]=tree[node].V[j][i]=s;
}
}
return;
}
int mid=tl+tr>>1;
if(y<=mid) updateH(node*2, tl, mid, y);
else updateH(node*2+1, mid+1, tr, y);
add(tree[node], tree[node*2], tree[node*2+1], mid);
}
void updateV(int node, int tl, int tr, int y)
{
int mid=tl+tr>>1;
if(y==mid) { add(tree[node], tree[node*2], tree[node*2+1], mid); return; }
if(y<=mid) updateV(node*2, tl, mid, y);
else updateV(node*2+1, mid+1, tr, y);
add(tree[node], tree[node*2], tree[node*2+1], mid);
}
void changeH(int P, int Q, int W)
{
H[P][Q]=W;
updateH(1, 0, R-1, P);
}
void changeV(int P, int Q, int W)
{
V[P][Q]=W;
updateV(1, 0, R-1, P);
}
int escape(int V1, int V2)
{
return tree[1].V[V1][V2];
}
Compilation message
grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
wombats.cpp: In function 'void init(int, int, int)':
wombats.cpp:54:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
wombats.cpp: In function 'void updateH(int, int, int, int)':
wombats.cpp:86:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
wombats.cpp: In function 'void updateV(int, int, int, int)':
wombats.cpp:94:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
9592 KB |
Output is correct |
2 |
Correct |
14 ms |
9464 KB |
Output is correct |
3 |
Correct |
101 ms |
12284 KB |
Output is correct |
4 |
Correct |
14 ms |
9464 KB |
Output is correct |
5 |
Correct |
14 ms |
9464 KB |
Output is correct |
6 |
Correct |
7 ms |
760 KB |
Output is correct |
7 |
Correct |
5 ms |
760 KB |
Output is correct |
8 |
Correct |
6 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
888 KB |
Output is correct |
2 |
Correct |
5 ms |
760 KB |
Output is correct |
3 |
Correct |
6 ms |
760 KB |
Output is correct |
4 |
Correct |
6 ms |
1016 KB |
Output is correct |
5 |
Correct |
7 ms |
1016 KB |
Output is correct |
6 |
Correct |
6 ms |
1016 KB |
Output is correct |
7 |
Correct |
6 ms |
1016 KB |
Output is correct |
8 |
Correct |
6 ms |
888 KB |
Output is correct |
9 |
Correct |
6 ms |
1016 KB |
Output is correct |
10 |
Correct |
6 ms |
1016 KB |
Output is correct |
11 |
Correct |
92 ms |
3324 KB |
Output is correct |
12 |
Correct |
6 ms |
1016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
955 ms |
9772 KB |
Output is correct |
2 |
Correct |
881 ms |
9720 KB |
Output is correct |
3 |
Correct |
1008 ms |
9848 KB |
Output is correct |
4 |
Correct |
894 ms |
9976 KB |
Output is correct |
5 |
Correct |
929 ms |
9848 KB |
Output is correct |
6 |
Correct |
5 ms |
760 KB |
Output is correct |
7 |
Correct |
6 ms |
760 KB |
Output is correct |
8 |
Correct |
5 ms |
760 KB |
Output is correct |
9 |
Correct |
4345 ms |
9872 KB |
Output is correct |
10 |
Correct |
6 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
18168 KB |
Output is correct |
2 |
Correct |
22 ms |
18168 KB |
Output is correct |
3 |
Correct |
22 ms |
18168 KB |
Output is correct |
4 |
Correct |
75 ms |
19596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
938 ms |
9720 KB |
Output is correct |
2 |
Correct |
870 ms |
9592 KB |
Output is correct |
3 |
Correct |
998 ms |
10052 KB |
Output is correct |
4 |
Correct |
923 ms |
9976 KB |
Output is correct |
5 |
Correct |
927 ms |
9720 KB |
Output is correct |
6 |
Correct |
20 ms |
18168 KB |
Output is correct |
7 |
Correct |
22 ms |
18168 KB |
Output is correct |
8 |
Correct |
21 ms |
18168 KB |
Output is correct |
9 |
Correct |
62 ms |
19576 KB |
Output is correct |
10 |
Correct |
14 ms |
9464 KB |
Output is correct |
11 |
Correct |
13 ms |
9464 KB |
Output is correct |
12 |
Correct |
106 ms |
12284 KB |
Output is correct |
13 |
Correct |
13 ms |
9464 KB |
Output is correct |
14 |
Correct |
13 ms |
9464 KB |
Output is correct |
15 |
Correct |
6 ms |
760 KB |
Output is correct |
16 |
Correct |
6 ms |
760 KB |
Output is correct |
17 |
Correct |
6 ms |
760 KB |
Output is correct |
18 |
Correct |
6 ms |
1016 KB |
Output is correct |
19 |
Correct |
6 ms |
1016 KB |
Output is correct |
20 |
Correct |
6 ms |
1016 KB |
Output is correct |
21 |
Correct |
6 ms |
1016 KB |
Output is correct |
22 |
Correct |
6 ms |
888 KB |
Output is correct |
23 |
Correct |
6 ms |
1064 KB |
Output is correct |
24 |
Correct |
6 ms |
1016 KB |
Output is correct |
25 |
Correct |
91 ms |
3448 KB |
Output is correct |
26 |
Correct |
6 ms |
1020 KB |
Output is correct |
27 |
Correct |
4319 ms |
9824 KB |
Output is correct |
28 |
Runtime error |
3992 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
948 ms |
9720 KB |
Output is correct |
2 |
Correct |
875 ms |
9720 KB |
Output is correct |
3 |
Correct |
1006 ms |
9848 KB |
Output is correct |
4 |
Correct |
902 ms |
9976 KB |
Output is correct |
5 |
Correct |
928 ms |
9724 KB |
Output is correct |
6 |
Correct |
20 ms |
18168 KB |
Output is correct |
7 |
Correct |
21 ms |
18168 KB |
Output is correct |
8 |
Correct |
24 ms |
18172 KB |
Output is correct |
9 |
Correct |
66 ms |
19576 KB |
Output is correct |
10 |
Correct |
14 ms |
9464 KB |
Output is correct |
11 |
Correct |
14 ms |
9464 KB |
Output is correct |
12 |
Correct |
105 ms |
12360 KB |
Output is correct |
13 |
Correct |
17 ms |
9464 KB |
Output is correct |
14 |
Correct |
19 ms |
9464 KB |
Output is correct |
15 |
Runtime error |
8552 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
16 |
Halted |
0 ms |
0 KB |
- |