oj.uz

Submission #204369

# Submission time Handle Problem Language Result Execution time Memory
204369 2020-02-25T14:21:12 Z mhy908 Wombats (IOI13_wombats) C++14
12 / 100
 597 ms 262148 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 222 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1784 KB Output is correct
2 Correct 5 ms 1784 KB Output is correct
3 Correct 6 ms 1656 KB Output is correct
4 Correct 7 ms 1784 KB Output is correct
5 Correct 7 ms 1784 KB Output is correct
6 Correct 7 ms 1784 KB Output is correct
7 Correct 7 ms 1784 KB Output is correct
8 Correct 7 ms 1784 KB Output is correct
9 Correct 7 ms 1784 KB Output is correct
10 Correct 7 ms 1784 KB Output is correct
11 Correct 112 ms 2808 KB Output is correct
12 Correct 8 ms 1784 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 595 ms 17272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 228 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 597 ms 17144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 584 ms 17144 KB Output isn't correct
2 Halted 0 ms 0 KB -