| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 67962 | andy627 | 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.
#include "wombats.h"
#include <stdio.h>
#include <algorithm>
#define ele (1<<9)
#define INF 2e9
using namespace std;
int n,m;
int h[5001][200],v[5001][200];
int sum[5001][200];
int seg[1024][200][200];
void make_leaf_(int p){
int cnt=min(10,m-1-p*10);
int dist[10][200][200],mer[10][200][200]; ///distance and merge
for(int r=0;r<cnt;r++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) dist[r][i][j]=mer[r][i][j]=INF;
}
}
//
vector<int> vl[200],vr[200];
for(int r=0;r<cnt;r++){
for(int i=0;i<n;i++) vl[i].clear(),vr[i].clear();
vl[n-1].push_back(0); vl[n-1].push_back(n-1);
vr[n-1].push_back(0); vr[n-1].push_back(n-1);
for(int g=n-1;g>=0;g--){
if(g>0) vl[g-1].push_back(0),vr[g-1].push_back(0);
for(int i=0;i+g<n;i++){
int mnl=-1,mnr=-1;
for(int j=vl[g][i];j<=vl[g][i+1];j++){
if(dist[r][i][i+g]>abs(sum[p*10+r][i]-sum[p*10+r][j])+v[p*10+r][j]+abs(sum[p*10+r+1][j]-sum[p*10+r+1][i+g])){
dist[r][i][i+g]=abs(sum[p*10+r][i]-sum[p*10+r][j])+v[p*10+r][j]+abs(sum[p*10+r+1][j]-sum[p*10+r+1][i+g]);
mnl=j;
}
}
for(int j=vr[g][i];j<=vr[g][i+1];j++){
if(dist[r][i+g][i]>abs(sum[p*10+r][i+g]-sum[p*10+r][j])+v[p*10+r][j]+abs(sum[p*10+r+1][j]-sum[p*10+r+1][i])){
dist[r][i+g][i]=abs(sum[p*10+r][i+g]-sum[p*10+r][j])+v[p*10+r][j]+abs(sum[p*10+r+1][j]-sum[p*10+r+1][i]);
mnr=j;
}
}
if(g>0) vl[g-1].push_back(mnl),vr[g-1].push_back(mnr);
}
if(g>0) vl[g-1].push_back(n-1),vr[g-1].push_back(n-1);
}
}
///get dist
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) mer[0][i][j]=dist[0][i][j];
}
for(int r=1;r<cnt;r++){
for(int i=0;i<n;i++) vl[i].clear(),vr[i].clear();
vl[n-1].push_back(0); vl[n-1].push_back(n-1);
vr[n-1].push_back(0); vr[n-1].push_back(n-1);
for(int g=n-1;g>=0;g--){
if(g>0) vl[g-1].push_back(0),vr[g-1].push_back(0);
for(int i=0;i+g<n;i++){
int mnl=-1,mnr=-1;
for(int j=vl[g][i];j<=vl[g][i+1];j++){
if(mer[r][i][i+g]>mer[r-1][i][j]+dist[r][j][i+g]){
mer[r][i][i+g]=mer[r-1][i][j]+dist[r][j][i+g];
mnl=j;
}
}
for(int j=vr[g][i];j<=vr[g][i+1];j++){
if(mer[r][i+g][i]>mer[r-1][i+g][j]+dist[r][j][i]){
mer[r][i+g][i]=mer[r-1][i+g][j]+dist[r][j][i];
mnr=j;
}
}
if(g>0) vl[g-1].push_back(mnl),vr[g-1].push_back(mnr);
}
if(g>0) vl[g-1].push_back(n-1),vr[g-1].push_back(n-1);
}
}
//
// TODO
/// get mer
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
seg[p+ele][i][j]=mer[cnt-1][i][j];
}
}
}
void update_(int w){
int c1=w<<1,c2=w<<1|1;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++) seg[w][i][j]=INF;
}
//
vector<int> vl[200],vr[200];
vl[n-1].push_back(0); vl[n-1].push_back(n-1);
vr[n-1].push_back(0); vr[n-1].push_back(n-1);
for(int g=n-1;g>=0;g--){
if(g>0) vl[g-1].push_back(0),vr[g-1].push_back(0);
for(int i=0;i+g<n;i++){
int mnl=-1,mnr=-1;
for(int j=vl[g][i];j<=vl[g][i+1];j++){
if(seg[w][i][i+g]>seg[c1][i][j]+seg[c2][j][i+g]){
seg[w][i][i+g]=seg[c1][i][j]+seg[c2][j][i+g];
mnl=j;
}
}
for(int j=vr[g][i];j<=vr[g][i+1];j++){
if(seg[w][i+g][i]>seg[c1][i+g][j]+seg[c2][j][i]){
seg[w][i+g][i]=seg[c1][i+g][j]+seg[c2][j][i];
mnr=j;
}
}
if(g>0) vl[g-1].push_back(mnl),vr[g-1].push_back(mnr);
}
if(g>0) vl[g-1].push_back(n-1),vr[g-1].push_back(n-1);
}
//
// TODO
}
void insert_(int w,int l,int r,int p){
if(l>r) return;
if(p==l && p==r){
make_leaf_(w-ele);
return;
}
int m=(l+r)>>1;
if(p<=m) insert_(w<<1,l,m,p);
else insert_(w<<1|1,m+1,r,p);
update_(w);
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
m=R; n=C;
for(int i=0;i<m;i++) for(int j=0;j<n-1;j++) h[i][j]=H[i][j];
for(int i=0;i<m-1;i++) for(int j=0;j<n;j++) v[i][j]=V[i][j];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++) sum[i][j+1]=sum[i][j]+h[i][j];
}
for(int i=0;i<=(m-1)/10;i++) make_leaf_(i);
for(int i=ele-1;i>0;i--) update_(i);
}
void changeH(int P, int Q, int W) {
h[P][Q]=W;
for(int j=0;j<n;j++) sum[P][j+1]=sum[P][j]+h[P][j];
insert_(1,0,ele-1,max(0,(P-1)/10));
}
void changeV(int P, int Q, int W) {
v[P][Q]=W;
insert_(1,0,ele-1,P/10);
}
int escape(int V1, int V2) {
return seg[1][V1][V2];
}