oj.uz

Submission #586847

# Submission time Handle Problem Language Result Execution time Memory
586847 2022-06-30T18:09:10 Z FatihSolak Wombats (IOI13_wombats) C++17
76 / 100
 2674 ms 202584 KB 
#include "wombats.h"
#include <bits/stdc++.h>
#define R 5005
#define C 205
using namespace std;
const int block = 40;
int r,c;
int h[R][C];
int w[R][C];
int opt[C][C];
struct node{
    int a[C][C];
    int l,r;
    node(int init){
        for(int i = 0;i<C;i++){
            for(int j = 0;j<C;j++){
                a[i][j] = init;
            }
        }
    }
};
node merge(node a,node b){
    node ret(1e9);
    for(int dif = -c-1;dif < c ;dif++){
        for(int i = max(0,-dif);i + dif<c;i++){
            int j = dif + i;
            int l = 0,r = c-1;
            if(j)
                l = opt[i][j-1];
            if(i + 1 != c)
                r = opt[i+1][j];
            for(int x = l;x<=r;x++){
                if(a.a[i][x] + b.a[x][j] < ret.a[i][j]){
                    ret.a[i][j] = a.a[i][x] + b.a[x][j];
                    opt[i][j] = x;
                }
            }
        }
    }
    return ret;
}
struct SegTree{
    vector<node> t;
    int n;
    void init(int size){
        n = size;
        t.assign(4*n,1e9);
        build(1,0,n-1);
    }
    void build(int v,int tl,int tr){
        t[v].l = tl * block;
        t[v].r = min(r-1,(tr + 1) * block - 1);
        if(tl == tr){
            for(int i = 0;i<c;i++){
                t[v].a[i][i] = 0;
                for(int j = t[v].l;j<=t[v].r;j++){
                    for(int d=1;d<c;d++){
                        t[v].a[i][d] = min(t[v].a[i][d],t[v].a[i][d-1] + h[j][d-1]);
                    }
                    for(int d=c-2;d>=0;d--){
                        t[v].a[i][d] = min(t[v].a[i][d],t[v].a[i][d+1] + h[j][d]);
                    }
                    for(int d=0;d<c;d++){
                        t[v].a[i][d] = t[v].a[i][d] + w[j][d];
                    }
                }
            }
            return;
        }
        int tm = (tl + tr)/2;
        build(v*2,tl,tm);
        build(v*2+1,tm+1,tr);
        t[v] = merge(t[v*2],t[v*2+1]);
    }
    void upd(int v,int tl,int tr,int pos){
        t[v].l = tl * block;
        t[v].r = min(r-1,(tr + 1) * block - 1);
        if(tl == tr){
            for(int i = 0;i<c;i++){
                t[v].a[i][i] = 0;
                for(int j = t[v].l;j<=t[v].r;j++){
                    for(int d=1;d<c;d++){
                        t[v].a[i][d] = min(t[v].a[i][d],t[v].a[i][d-1] + h[j][d-1]);
                    }
                    for(int d=c-2;d>=0;d--){
                        t[v].a[i][d] = min(t[v].a[i][d],t[v].a[i][d+1] + h[j][d]);
                    }
                    for(int d=0;d<c;d++){
                        t[v].a[i][d] = t[v].a[i][d] + w[j][d];
                    }
                }
            }
            return;
        }
        int tm = (tl + tr)/2;
        if(pos <= tm)
            upd(v*2,tl,tm,pos);
        else upd(v*2+1,tm+1,tr,pos);
        t[v] = merge(t[v*2],t[v*2+1]);
    }

    void upd(int pos){
        upd(1,0,n-1,pos);
    }

}tree;

void init(int r_, int c_, int h_[5000][200], int v_[5000][200]) {
    r = r_;
    c = c_;
    for(int i = 0;i<r;i++){
        for(int j = 0;j<c;j++){
            h[i][j] = h_[i][j];
            w[i][j] = v_[i][j];
        }
    }
    tree.init((r+block-1) / block);
}

void changeH(int p, int q, int x) {
    h[p][q] = x;
    tree.upd(p/block);
}

void changeV(int p, int q, int x) {
    w[p][q] = x;
    if(p % block == 0 && p)
        tree.upd(p/block - 1);
    tree.upd(p/block);
}

int escape(int v1, int v2) {
    return tree.t[1].a[v1][v2];
}

Compilation message

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 95900 KB Output is correct
2 Correct 198 ms 95940 KB Output is correct
3 Correct 254 ms 97524 KB Output is correct
4 Correct 200 ms 95932 KB Output is correct
5 Correct 193 ms 95916 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct
8 Correct 1 ms 1108 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB Output is correct
2 Correct 1 ms 1108 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct
8 Correct 1 ms 1108 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 1 ms 1108 KB Output is correct
11 Correct 67 ms 2132 KB Output is correct
12 Correct 1 ms 1152 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 3352 KB Output is correct
2 Correct 374 ms 3284 KB Output is correct
3 Correct 327 ms 3284 KB Output is correct
4 Correct 329 ms 3368 KB Output is correct
5 Correct 363 ms 3284 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 1 ms 1108 KB Output is correct
8 Correct 1 ms 1108 KB Output is correct
9 Correct 1743 ms 3284 KB Output is correct
10 Correct 1 ms 1108 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 99904 KB Output is correct
2 Correct 201 ms 99936 KB Output is correct
3 Correct 264 ms 99880 KB Output is correct
4 Correct 226 ms 100668 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 245 ms 3412 KB Output is correct
2 Correct 339 ms 3364 KB Output is correct
3 Correct 332 ms 3284 KB Output is correct
4 Correct 336 ms 3252 KB Output is correct
5 Correct 364 ms 3284 KB Output is correct
6 Correct 194 ms 99880 KB Output is correct
7 Correct 194 ms 99880 KB Output is correct
8 Correct 237 ms 99836 KB Output is correct
9 Correct 271 ms 100628 KB Output is correct
10 Correct 186 ms 95868 KB Output is correct
11 Correct 183 ms 95924 KB Output is correct
12 Correct 258 ms 97572 KB Output is correct
13 Correct 212 ms 95948 KB Output is correct
14 Correct 203 ms 95952 KB Output is correct
15 Correct 1 ms 1108 KB Output is correct
16 Correct 1 ms 1108 KB Output is correct
17 Correct 1 ms 1108 KB Output is correct
18 Correct 1 ms 1108 KB Output is correct
19 Correct 1 ms 1108 KB Output is correct
20 Correct 1 ms 1108 KB Output is correct
21 Correct 2 ms 1108 KB Output is correct
22 Correct 1 ms 1108 KB Output is correct
23 Correct 1 ms 1108 KB Output is correct
24 Correct 1 ms 1108 KB Output is correct
25 Correct 69 ms 2124 KB Output is correct
26 Correct 1 ms 1108 KB Output is correct
27 Correct 1731 ms 3284 KB Output is correct
28 Correct 2593 ms 100392 KB Output is correct
29 Correct 2485 ms 82996 KB Output is correct
30 Correct 2503 ms 83088 KB Output is correct
31 Correct 2674 ms 101292 KB Output is correct
32 Correct 1 ms 1108 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 3356 KB Output is correct
2 Correct 346 ms 3368 KB Output is correct
3 Correct 334 ms 3284 KB Output is correct
4 Correct 327 ms 3284 KB Output is correct
5 Correct 368 ms 3284 KB Output is correct
6 Correct 205 ms 99872 KB Output is correct
7 Correct 221 ms 100004 KB Output is correct
8 Correct 228 ms 99788 KB Output is correct
9 Correct 229 ms 100612 KB Output is correct
10 Correct 202 ms 96048 KB Output is correct
11 Correct 181 ms 95948 KB Output is correct
12 Correct 250 ms 97492 KB Output is correct
13 Correct 218 ms 95884 KB Output is correct
14 Correct 183 ms 95960 KB Output is correct
15 Runtime error 343 ms 202584 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -