oj.uz

Submission #204371

# Submission time Handle Problem Language Result Execution time Memory
204371 2020-02-25T14:25:07 Z mhy908 Wombats (IOI13_wombats) C++14
100 / 100
 14784 ms 119392 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, e);
        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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1012 ms 100296 KB Output is correct
2 Correct 979 ms 100344 KB Output is correct
3 Correct 1084 ms 103032 KB Output is correct
4 Correct 1002 ms 100344 KB Output is correct
5 Correct 963 ms 100472 KB Output is correct
6 Correct 6 ms 1656 KB Output is correct
7 Correct 6 ms 1784 KB Output is correct
8 Correct 6 ms 1784 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1784 KB Output is correct
2 Correct 6 ms 1656 KB Output is correct
3 Correct 6 ms 1784 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 95 ms 2816 KB Output is correct
12 Correct 7 ms 1784 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 4600 KB Output is correct
2 Correct 262 ms 4600 KB Output is correct
3 Correct 631 ms 4600 KB Output is correct
4 Correct 324 ms 4600 KB Output is correct
5 Correct 467 ms 4600 KB Output is correct
6 Correct 6 ms 1784 KB Output is correct
7 Correct 6 ms 1656 KB Output is correct
8 Correct 6 ms 1656 KB Output is correct
9 Correct 2163 ms 4692 KB Output is correct
10 Correct 6 ms 1784 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1327 ms 108536 KB Output is correct
2 Correct 972 ms 108408 KB Output is correct
3 Correct 1338 ms 108412 KB Output is correct
4 Correct 1334 ms 109944 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 4600 KB Output is correct
2 Correct 276 ms 4600 KB Output is correct
3 Correct 613 ms 4728 KB Output is correct
4 Correct 334 ms 4728 KB Output is correct
5 Correct 465 ms 4732 KB Output is correct
6 Correct 1320 ms 108464 KB Output is correct
7 Correct 971 ms 108408 KB Output is correct
8 Correct 1333 ms 108536 KB Output is correct
9 Correct 1326 ms 110072 KB Output is correct
10 Correct 994 ms 100344 KB Output is correct
11 Correct 999 ms 100216 KB Output is correct
12 Correct 1098 ms 103032 KB Output is correct
13 Correct 1014 ms 100600 KB Output is correct
14 Correct 958 ms 100344 KB Output is correct
15 Correct 6 ms 1656 KB Output is correct
16 Correct 6 ms 1784 KB Output is correct
17 Correct 6 ms 1656 KB Output is correct
18 Correct 7 ms 1912 KB Output is correct
19 Correct 7 ms 1840 KB Output is correct
20 Correct 7 ms 1784 KB Output is correct
21 Correct 7 ms 1784 KB Output is correct
22 Correct 7 ms 1788 KB Output is correct
23 Correct 7 ms 1784 KB Output is correct
24 Correct 8 ms 1784 KB Output is correct
25 Correct 99 ms 4216 KB Output is correct
26 Correct 7 ms 1784 KB Output is correct
27 Correct 2214 ms 4656 KB Output is correct
28 Correct 4655 ms 112640 KB Output is correct
29 Correct 4195 ms 109484 KB Output is correct
30 Correct 4398 ms 109476 KB Output is correct
31 Correct 4276 ms 114368 KB Output is correct
32 Correct 6 ms 1784 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 4600 KB Output is correct
2 Correct 269 ms 4472 KB Output is correct
3 Correct 619 ms 4600 KB Output is correct
4 Correct 334 ms 4728 KB Output is correct
5 Correct 468 ms 4732 KB Output is correct
6 Correct 1318 ms 108408 KB Output is correct
7 Correct 999 ms 108396 KB Output is correct
8 Correct 1326 ms 108504 KB Output is correct
9 Correct 1332 ms 109972 KB Output is correct
10 Correct 982 ms 100344 KB Output is correct
11 Correct 1022 ms 100408 KB Output is correct
12 Correct 1079 ms 103032 KB Output is correct
13 Correct 1010 ms 100376 KB Output is correct
14 Correct 1006 ms 100472 KB Output is correct
15 Correct 2873 ms 117880 KB Output is correct
16 Correct 14784 ms 119392 KB Output is correct
17 Correct 6 ms 1784 KB Output is correct
18 Correct 5 ms 1660 KB Output is correct
19 Correct 6 ms 1784 KB Output is correct
20 Correct 7 ms 1784 KB Output is correct
21 Correct 8 ms 1856 KB Output is correct
22 Correct 7 ms 1848 KB Output is correct
23 Correct 8 ms 1852 KB Output is correct
24 Correct 8 ms 1784 KB Output is correct
25 Correct 8 ms 1784 KB Output is correct
26 Correct 7 ms 1784 KB Output is correct
27 Correct 98 ms 4220 KB Output is correct
28 Correct 7 ms 1784 KB Output is correct
29 Correct 2418 ms 4664 KB Output is correct
30 Correct 4981 ms 112384 KB Output is correct
31 Correct 13364 ms 116824 KB Output is correct
32 Correct 13313 ms 116644 KB Output is correct
33 Correct 4257 ms 109320 KB Output is correct
34 Correct 12486 ms 113628 KB Output is correct
35 Correct 4297 ms 109432 KB Output is correct
36 Correct 12524 ms 113328 KB Output is correct
37 Correct 4422 ms 114104 KB Output is correct
38 Correct 12432 ms 117584 KB Output is correct
39 Correct 6 ms 1784 KB Output is correct
40 Correct 13012 ms 113684 KB Output is correct