Submission #790616

#	Time	Username	Problem	Language	Result	Execution time	Memory
790616		Ronin13	Wombats (IOI13_wombats)	C++17	76 / 100	2008 ms	262144 KiB

wombats

#include <bits/stdc++.h>
#include "wombats.h"
#define ll long long 
#define ull unsigned ll
#define f first
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 501;
int h[5000][200];
int v[5000][200];
int r, c;
int s;
struct node{
    //vector <int> h;
    vector <int> w;
    vector <vector <int> > cost;
    node(){
        cost.resize(c);
        for(int i = 0; i < c; i++)
        cost[i].resize(c);
        w.resize(c);
    }
    node(int c){
        cost.resize(c);
        for(int i = 0; i < c; i++)
        cost[i].resize(c);
        w.resize(c);
    }
}t[3 * nmax];


node b[nmax];
node merg(node a, node b){
    node c;
    c.w = b.w;
    int n = a.w.size();
    c.cost.resize(n);
    vector <vector <int> > opt;
    opt.resize(n);
    for(int i= 0; i < n; i++)
        c.cost[i].resize(n), opt[i].resize(n);
    for(int i = 0; i < n; i++){
        int mn = 1e9 + 1, mni;
        for(int j= 0; j < n; j++){
            int val = a.cost[n - 1][j] + a.w[j] + b.cost[j][i];
            if(val < mn)
                mn = val, mni = j;
        }
        opt[n - 1][i] = mni, c.cost[n - 1][i] = mn;
    }
    for(int i = n - 2; i >= 0; i--){
        int mn = 1e9 + 1,mni;
        for(int j = 0; j < n; j++){
            int val = a.cost[i][j] + a.w[j] + b.cost[j][0];
            if(val < mn)
                mn = val, mni = j;
        }
        opt[i][0] = mni, c.cost[i][0] = mn;
        for(int j = 1; j <= n - 1; j++){
            int mn = 1e9 + 1, mni = j;
            for(int x = opt[i][j - 1]; x <= opt[i + 1][j]; x++){
                int val = a.cost[i][x] + a.w[x] + b.cost[x][j];
                if(val < mn)
                    mn = val, mni = x;
            }
            opt[i][j] = mni, c.cost[i][j] = mn;
        }
    }
    return c;
}

void update(int v, int l, int r, int pos, node a){
    if(l > pos || r < pos)
    return;
    if(l == r){
        t[v] = a;
        return;
    }
    int m = (l + r) / 2;
    update(2 * v, l, m, pos, a);
    update(2 * v + 1, m + 1, r, pos, a);
    t[v] = merg(t[2 * v], t[2 * v + 1]);
}


void init(int R, int C, int H[5000][200], int V[5000][200]) {
    /* ... */
    r = R, c = C;
    for(int i = 0; i < 5000; i++){
        for(int j = 0; j < 200; j++)
        h[i][j] = H[i][j], v[i][j] = V[i][j]; 
     
    }
    for(int i = 0; i < r; i++){
        node a = {c};
        for(int j = 0; j < c; j++)
            a.w[j] = V[i][j];
        for(int x = 0; x < c; x++){
            a.cost[x][x] = 0;
            for(int y = x + 1; y < c; ++y){
                a.cost[x][y] = a.cost[x][y - 1] + H[i][y - 1];
            }
            for(int y = x - 1; y >= 0; y--)
                a.cost[x][y] = a.cost[x][y + 1] + H[i][y];
        }
        if(i % 10 == 0)
            b[i / 10] = a;
        else b[i / 10] =  merg(b[i / 10], a);
        s = i / 10;
    }
    for(int i = 0; i <= 3 * s; i++)
        t[i] = {c};
    for(int i = 0; i <= s; i++)
        update(1, 0, s, i, b[i]);
    
}

void update_block(int o){
   // b[o] = a[o * 10];
    int xx = o * 10;
    for(int i = xx; i < min(r, xx + 10); i++){
        node a = {c};
        for(int j = 0; j < c; j++)
            a.w[j] = v[i][j];
        for(int x = 0; x < c; x++){
            a.cost[x][x] = 0;
            for(int y = x + 1; y < c; ++y){
                a.cost[x][y] = a.cost[x][y - 1] + h[i][y - 1];
            }
            for(int y = x - 1; y >= 0; y--)
                a.cost[x][y] = a.cost[x][y + 1] + h[i][y];
        }
        if(i % 10 == 0)
            b[i / 10] = a;
        else b[i / 10] =  merg(b[i / 10], a);
    }
    update(1, 0, s, o, b[o]);
}

void changeH(int p, int q, int w) {
    /* ... */
    h[p][q] = w;
    update_block(p / 10);
}

void changeV(int p, int q, int w) {
    /* ... */
    
    v[p][q] = w;
    
    update_block(p / 10);
}

int escape(int V1, int V2) {
    return t[1].cost[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;
      |      ^~~
wombats.cpp: In function 'node merg(node, node)':
wombats.cpp:61:19: warning: 'mni' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |         opt[i][0] = mni, c.cost[i][0] = mn;
wombats.cpp:52:23: warning: 'mni' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |         opt[n - 1][i] = mni, c.cost[n - 1][i] = mn;

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 0 / 24