oj.uz

Submission #586846

# Submission time Handle Problem Language Result Execution time Memory
586846 2022-06-30T18:08:09 Z FatihSolak Wombats (IOI13_wombats) C++17
76 / 100
 2036 ms 262144 KB 
#include "wombats.h"
#include <bits/stdc++.h>
#define R 5005
#define C 205
using namespace std;
const int block = 20;
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 251 ms 178312 KB Output is correct
2 Correct 275 ms 178360 KB Output is correct
3 Correct 348 ms 179872 KB Output is correct
4 Correct 286 ms 178376 KB Output is correct
5 Correct 268 ms 178352 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 1180 KB Output is correct
8 Correct 1 ms 1108 KB Output is correct
9 Correct 2 ms 1108 KB Output is correct
10 Correct 2 ms 1108 KB Output is correct
11 Correct 86 ms 2120 KB Output is correct
12 Correct 1 ms 1108 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 4832 KB Output is correct
2 Correct 220 ms 4820 KB Output is correct
3 Correct 221 ms 4740 KB Output is correct
4 Correct 212 ms 4820 KB Output is correct
5 Correct 218 ms 4820 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 1029 ms 4844 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 261 ms 182280 KB Output is correct
2 Correct 288 ms 182292 KB Output is correct
3 Correct 288 ms 182240 KB Output is correct
4 Correct 322 ms 182980 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 4840 KB Output is correct
2 Correct 212 ms 4820 KB Output is correct
3 Correct 217 ms 4848 KB Output is correct
4 Correct 222 ms 4820 KB Output is correct
5 Correct 226 ms 4828 KB Output is correct
6 Correct 264 ms 182284 KB Output is correct
7 Correct 308 ms 182288 KB Output is correct
8 Correct 298 ms 182204 KB Output is correct
9 Correct 328 ms 183080 KB Output is correct
10 Correct 276 ms 178268 KB Output is correct
11 Correct 276 ms 178340 KB Output is correct
12 Correct 335 ms 179920 KB Output is correct
13 Correct 271 ms 178392 KB Output is correct
14 Correct 262 ms 178360 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 1 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 68 ms 2212 KB Output is correct
26 Correct 1 ms 1108 KB Output is correct
27 Correct 1038 ms 4848 KB Output is correct
28 Correct 1974 ms 182852 KB Output is correct
29 Correct 1901 ms 150248 KB Output is correct
30 Correct 1954 ms 150416 KB Output is correct
31 Correct 2036 ms 183812 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 202 ms 4832 KB Output is correct
2 Correct 234 ms 4736 KB Output is correct
3 Correct 223 ms 4732 KB Output is correct
4 Correct 221 ms 4848 KB Output is correct
5 Correct 215 ms 4820 KB Output is correct
6 Correct 306 ms 182288 KB Output is correct
7 Correct 254 ms 182292 KB Output is correct
8 Correct 283 ms 182284 KB Output is correct
9 Correct 305 ms 183084 KB Output is correct
10 Correct 311 ms 178308 KB Output is correct
11 Correct 252 ms 178372 KB Output is correct
12 Correct 374 ms 179984 KB Output is correct
13 Correct 270 ms 178288 KB Output is correct
14 Correct 282 ms 178360 KB Output is correct
15 Runtime error 416 ms 262144 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -