Submission #204369

#	Time	Username	Problem	Language	Result	Execution time	Memory
204369		mhy908	Wombats (IOI13_wombats)	C++14	12 / 100	597 ms	262148 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
const int inf=1000000000;

int r, c, e;
int h[5010][210], v[5010][210];

struct SEGMENT_TREE{
    struct DATA{
        int link[210][210];
        DATA(){memset(link, 0, sizeof link);}
    };
    struct NODE{
        NODE *l, *r;
        DATA dp;
        NODE(){l=r=0;}
    }*root;
    SEGMENT_TREE(){root=new NODE;}
    DATA f(DATA a, DATA b){
        DATA ret, knu;
        for(int diff=1-c; diff<=c-1; diff++){
            for(int i=1; i<=c; i++){
                int j=i+diff;
                if(j<1||j>c)continue;
                ret.link[i][j]=inf;
                int ll, rr;
                if(knu.link[i][j-1])ll=knu.link[i][j-1];
                else ll=1;
                if(knu.link[i+1][j])rr=knu.link[i+1][j];
                else rr=c;
                for(int k=ll; k<=rr; k++){
                    if(ret.link[i][j]>a.link[i][k]+b.link[k][j]){
                        ret.link[i][j]=a.link[i][k]+b.link[k][j];
                        knu.link[i][j]=k;
                    }
                }
            }
        }
        return ret;
    }
    DATA naive(int s, int e){
        DATA ret, tmp1, tmp2;
        for(int i=1; i<=c; i++){
            for(int j=1; j<=c; j++){
                if(i!=j)ret.link[i][j]=inf;
            }
        }
        int sum[210];
        memset(sum, 0, sizeof sum);
        for(int i=s; i<=e+1; i++){
            for(int j=2; j<=c; j++)sum[j]=sum[j-1]+h[i][j-1];
            for(int j=1; j<=c; j++){
                for(int k=1; k<=c; k++){
                    tmp1.link[j][k]=ret.link[j][k];
                    if(i>s)tmp1.link[j][k]+=v[i-1][k];
                }
            }
            for(int j=1; j<=c; j++){
                for(int k=1; k<=c; k++){
                    tmp2.link[j][k]=abs(sum[j]-sum[k]);
                }
            }
            ret=f(tmp1, tmp2);
        }
        return ret;
    }
    void maketree(NODE* nd, int s, int e){
        if(e-s<20){
            nd->dp=naive(s, e);
            return;
        }
        nd->l=new NODE;
        nd->r=new NODE;
        int mid=(s+e)/2;
        maketree(nd->l, s, mid);
        maketree(nd->r, mid+1, r);
        nd->dp=f(nd->l->dp, nd->r->dp);
    }
    void maketree(){maketree(root, 1, r-1);}
    void update(NODE* nd, int num, int s, int e){
        if(e-s<20){
            nd->dp=naive(s, e);
            return;
        }
        int mid=(s+e)/2;
        if(num<=mid)update(nd->l, num, s, mid);
        else update(nd->r, num, mid+1, e);
        nd->dp=f(nd->l->dp, nd->r->dp);
    }
    void update(int num){update(root, num, 1, r-1);}
    int query(int a, int b){return root->dp.link[a][b];}
}seg;

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r=R, c=C;
    for(int i=1; i<=r; i++){
        for(int j=1; j<c; j++){
            h[i][j]=H[i-1][j-1];
        }
    }
    for(int i=1; i<r; i++){
        for(int j=1; j<=c; j++){
            v[i][j]=V[i-1][j-1];
        }
    }
    seg.maketree();
}

void changeH(int P, int Q, int W) {
    h[P+1][Q+1]=W;
    seg.update(P);
    seg.update(P+1);
}

void changeV(int P, int Q, int W) {
    v[P+1][Q+1]=W;
    seg.update(P+1);
}

int escape(int V1, int V2) {
    return seg.query(V1+1, V2+1);
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

• Subtask 1: 0 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 16
• Subtask 4: 0 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24