#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int,int>
#define f first
#define s second
const int inf=1e9;
const int N=5120;
const int C=205;
int opt[C][C];
int n,c;
int getopt(int i, int j) {
if (i<0 || j<0) return 0;
if (i>=c || j>=c) return c-1;
return opt[i][j];
}
struct sgt {
struct node {
int empty=1;
vector<vector<int>> v;
node() {
empty=1;
}
};
vector<node> t; int sz=1;
sgt(int n) {
while (sz<n) sz<<=1;
t.assign(2*sz,node());
}
void merge(int v, int a, int b) {
if (t[b].empty) {
t[v]=t[a];
return;
}
if (t[a].empty) {
t[v]=t[b];
return;
}
t[v].empty=0;
t[v].v.assign(c,vector<int>(c,inf));
for (int k=-c+1; k<c; ++k) {
for (int l=0; l<c; ++l) {
int r = l-k;
if (r<0 || r>=c) continue;
for (int m=getopt(l-1,r); m<=getopt(l,r+1); ++m) {
if (t[a].v[l][m]+t[b].v[m][r] < t[v].v[l][r]) {
t[v].v[l][r] = t[a].v[l][m]+t[b].v[m][r];
opt[l][r] = m;
}
}
}
}
}
void upd(int v, int l, int r, int i) {
if (r-l==1) return;
int m=(l+r)>>1;
if (i<m) upd(2*v+1,l,m,i);
else upd(2*v+2,m,r,i);
merge(v,2*v+1,2*v+2);
}
void set(int i, vector<vector<int>>&v) {
t[sz-1+i].v=v;
t[sz-1+i].empty=0;
upd(0,0,sz,i);
}
};
const int K=10;
sgt st(N/K);
int d[K*C][C];
int h[N][C];
int v[N][C];
bitset<2*C> vis;
void work(int i) {
vector<vector<int>> t(c,vector<int>(c,1e9));
for(int j=i; j<min(i+K,n-1); ++j) {
forn(p,c) {
vis.reset();
priority_queue<pi> q;
q.push({0,p});
while (q.size()) {
auto it=q.top(); q.pop();
int u=it.s, di=-it.f;
if (vis[u]) continue;
vis[u]=1;
if (u<c) {
if (u) q.push({-di-h[j][u-1],u-1});
if (u<c-1) q.push({-di-h[j][u],u+1});
q.push({-di-v[j][u],u+c});
} else {
d[p+c*(j-i)][u-c]=di;
if (u-c) q.push({-di-h[j+1][u-c-1],u-1});
if (u-c<c-1) q.push({-di-h[j+1][u-c],u+1});
}
}
}
}
auto f=t;
auto s=f;
forn(p,c) forn(q,c) s[p][q]=d[p][q];
for(int j=i+1; j<min(i+K,n-1); ++j) {
forn(p,c) {
forn(q,c) {
if (s[p][q]+d[q+(j-i)*c][p] < f[p][p]) {
f[p][p] = s[p][q]+d[q+(j-i)*c][p];
opt[p][p] = q;
}
}
}
for(int k=1; k<c; ++k) {
for (int l=0; l+k<c; ++l) {
int r=l+k;
for (int m=opt[l][r-1]; m<=opt[l+1][r]; ++m) {
if (s[l][m]+d[m+(j-i)*c][r] < f[l][r]) {
f[l][r] = s[l][m]+d[m+(j-i)*c][r];
opt[l][r]=m;
}
}
}
}
for(int k=1; k<c; ++k) {
for (int l=0; l+k<c; ++l) {
int r=l+k;
for (int m=opt[r-1][l]; m<=opt[r][l+1]; ++m) {
if (s[r][m]+d[m+(j-i)*c][l] < f[r][l]) {
f[r][l] = s[r][m]+d[m+(j-i)*c][l];
opt[r][l]=m;
}
}
}
}
s=f;
f=t;
}
st.set(i/K,s);
}
void init(int _n, int _c, int _h[][200], int _v[][200]) {
n=_n, c=_c;
forn(i,n) forn(j,c-1) h[i][j]=_h[i][j];
forn(i,n-1) forn(j,c) v[i][j]=_v[i][j];
for (int i=0; i<n-1; i+=K) {
work(i);
}
}
void changeH(int i, int j, int w) {
h[i][j]=w;
work((i/K)*K);
if ((i+1)/K*K != i/K*K) work((i+1)/K*K);
if (i) if ((i-1)/K*K != i/K*K) work((i-1)/K*K);
}
void changeV(int i, int j, int w) {
v[i][j]=w;
work((i/K)*K);
if ((i+1)/K*K != i/K*K) work((i+1)/K*K);
if (i) if ((i-1)/K*K != i/K*K) work((i-1)/K*K);
}
int escape(int i, int j) {
return st.t[0].v[i][j];
}
Compilation message
grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
15 | int res;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8276 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8276 KB |
Output is correct |
| 3 |
Correct |
60 ms |
11096 KB |
Output is correct |
| 4 |
Correct |
5 ms |
8276 KB |
Output is correct |
| 5 |
Correct |
5 ms |
8276 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
2 ms |
596 KB |
Output is correct |
| 5 |
Correct |
1 ms |
596 KB |
Output is correct |
| 6 |
Correct |
1 ms |
596 KB |
Output is correct |
| 7 |
Correct |
2 ms |
596 KB |
Output is correct |
| 8 |
Correct |
2 ms |
596 KB |
Output is correct |
| 9 |
Correct |
2 ms |
596 KB |
Output is correct |
| 10 |
Correct |
2 ms |
596 KB |
Output is correct |
| 11 |
Correct |
71 ms |
2988 KB |
Output is correct |
| 12 |
Correct |
2 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2027 ms |
2968 KB |
Output is correct |
| 2 |
Correct |
3339 ms |
2892 KB |
Output is correct |
| 3 |
Incorrect |
2180 ms |
2888 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
16336 KB |
Output is correct |
| 2 |
Correct |
12 ms |
16292 KB |
Output is correct |
| 3 |
Correct |
12 ms |
16356 KB |
Output is correct |
| 4 |
Correct |
47 ms |
17728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1969 ms |
2880 KB |
Output is correct |
| 2 |
Correct |
3299 ms |
2852 KB |
Output is correct |
| 3 |
Incorrect |
2189 ms |
3004 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2024 ms |
3008 KB |
Output is correct |
| 2 |
Correct |
3297 ms |
2852 KB |
Output is correct |
| 3 |
Incorrect |
2190 ms |
2976 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
