Submission #204367

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
204367	2020-02-25T14:19:00 Z	mhy908	Wombats (IOI13_wombats)	C++14	Compilation error	0 ms	0 KB

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<50){
            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<50){
            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

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 (*)[200], int (*)[200])':
wombats.cpp:96:13: error: expected ';' before ':' token
     r=R, c=C:
             ^
wombats.cpp:97:18: error: 'i' was not declared in this scope
     for(int i=1; i<=r; i++){
                  ^
wombats.cpp: In function 'void changeV(int, int, int)':
wombats.cpp:117:5: error: 'V' was not declared in this scope
     V[P+1][Q+1]=W;
     ^