| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 227220 | kig9981 | Wombats (IOI13_wombats) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include "wombats.h"
#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
const int B=20, SZ=1<<8;
int N, M, H[5000][200], PS[5000][200], V[5000][200], tree[2*SZ][200][200], md[SZ], D[200], D2[200];
void set_md(int bit=1, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
if(s==e) return;
set_md(2*bit,s,m);
set_md(2*bit+1,m+1,e);
md[bit]=min((m+1)*B-1,N-1);
}
int get_cost(int h, int s, int e)
{
if(s>e) swap(s,e);
return PS[h][e]-PS[h][s];
}
void dnc(int h, int s1, int e1, int s2, int e2)
{
int m2=(s2+e2)>>1, m=s1;
if(s2>e2) return;
for(int i=s1+1;i<=e1;i++) if(D[i]+get_cost(h,i,m2)<D[m]+get_cost(h,m,m2)) m=i;
D2[m2]=D[m]+get_cost(h,m,m2);
dnc(h,s1,m,s2,m2-1);
dnc(h,m,e1,m2+1,e2);
}
void dijk(int b)
{
for(int r=0;r<M;r++) {
for(int i=0;i<B && b*B+i<N;i++) {
if(i) {
for(int j=0;j<M;j++) D[j]=D2[j]+V[b*B+i-1][j];
}
else {
for(int j=0;j<M;j++) D[j]=(r!=j)*0x3fffffff;
}
dnc(b*B+i,0,M-1,0,M-1);
}
for(int j=0;j<M;j++) tree[SZ+b][r][j]=D2[j];
}
}
void dnc(int p, int l, int r, int b, int s1, int e1, int s2, int e2)
{
int m2=(s2+e2)>>1, m=s1;
if(s2>e2) return;
for(int i=s1+1;i<=e1;i++) if(tree[l][b][i]+V[md[p]][i]+tree[r][i][m2]<tree[l][b][m]+V[md[p]][m]+tree[r][m][m2]) m=i;
tree[p][b][m2]=tree[l][b][m]+V[md[p]][m]+tree[r][m][m2];
dnc(p,l,r,b,s1,m,s2,m2-1);
dnc(p,l,r,b,m,e1,m2+1,e2);
}
void init(int R, int C, int (*H)[200], int (*V)[200])
{
N=R; M=C;
for(int i=0;i<N;i++) for(int j=0;j<M-1;j++) {
::H[i][j]=H[i][j];
PS[i][j+1]=PS[i][j]+H[i][j];
}
for(int i=0;i<N-1;i++) for(int j=0;j<M;j++) ::V[i][j]=V[i][j];
for(int i=0;i<SZ;i++) {
if(i*B<N) dijk(i);
else for(int j=0;j<M;j++) for(int k=0;k<M;k++) tree[SZ+i][j][k]=(j!=k)*1000;
}
set_md();
for(int i=SZ;--i;) dnc(i,2*i,2*i+1,j,0,M-1,0,M-1);
}
void changeH(int P, int Q, int W)
{
H[P][Q]=W;
for(int j=0;j<M;j++) PS[P][j+1]=PS[P][j]+H[P][j];
dijk(P/B);
for(int n=SZ+P/B;n>>=1;) for(int j=0;j<M;j++) dnc(n,2*n,2*n+1,j,0,M-1,0,M-1);
}
void changeV(int P, int Q, int W)
{
V[P][Q]=W;
if(P/B==(P+1)/B) dijk(P/B);
for(int n=SZ+P/B;n>>=1;) for(int j=0;j<M;j++) dnc(n,2*n,2*n+1,j,0,M-1,0,M-1);
}
int escape(int V1, int V2)
{
return tree[1][V1][V2];
}