Submission #586854

#	Time	Username	Problem	Language	Result	Execution time	Memory
586854		FatihSolak	Wombats (IOI13_wombats)	C++17	100 / 100	8848 ms	111920 KiB

wombats

#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;
            }
        }
    }
}tmp(0);
node merge(node a,node b){
    for(int dif = -c-1;dif < c ;dif++){
        for(int i = max(0,-dif);i + max(0,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];
            tmp.a[i][j] = 1e9;
            for(int x = l;x<=r;x++){
                if(a.a[i][x] + b.a[x][j] < tmp.a[i][j]){
                    tmp.a[i][j] = a.a[i][x] + b.a[x][j];
                    opt[i][j] = x;
                }
            }
        }
    }
    return tmp;
}
struct SegTree{
    vector<node> t;
    int n;
    void init(int size){
        n = size;
        t.assign(4*n + 5,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){
        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 (stderr)

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24