Submission #1162639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162639		ty_mxzhn	Wombats (IOI13_wombats)	C++20	100 / 100	4451 ms	97216 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.begin();
#define all(x) x.begin(),x.end();
const int inf = 1e9 + 7;
const int BSZ = 20;
int R,C,H[5000][200],V[5000][200];
struct Node{
    int dist[200][200];;
    void update(int l , int r){
        // cout << "update : " << l << " " << r << endl;
        for(int i = 0;i<C;i++)
            for(int j = 0;j<C;j++)
                dist[i][j] = i == j ? 0 : inf;

        for(int x = l;x<=r;x++){
            int ndist[200][200];

            for(int a = 0;a<C;a++){
                int premax[C] , sufmax[C];
                for(int i = 0;i<C;i++){
                    if(i == 0)
                        premax[i] = dist[a][i] + (x == l ? 0 : V[x-1][i]);
                    else 
                        premax[i] = min(premax[i-1] + H[x][i-1] , dist[a][i] + (x == l ? 0 : V[x-1][i]));
                }
                for(int i = C-1;i>=0;i--){
                    if(i == C-1)
                        sufmax[i] = dist[a][i] + (x == l ? 0 : V[x-1][i]);
                    else 
                        sufmax[i] = min(sufmax[i+1] + H[x][i] , dist[a][i] + (x == l ? 0 : V[x-1][i]));
                }
                for(int i = 0;i<C;i++){
                    ndist[a][i] = min(premax[i] , sufmax[i]);
                }
            }

            for(int i = 0;i<200;i++)
                for(int j = 0;j<200;j++)
                    dist[i][j] = ndist[i][j];
        }
    }
    friend Node merge(Node &a , Node &b , int split){
        Node c;
        int opt[200][200];
        memset(opt , 0 , sizeof(opt));
        for(int x=C-1;x>=0;x--){
            for(int y = 0;y<C;y++){
                int lo = y == 0 ? 0 : opt[x][y-1];
                int hi = x == C-1 ? C-1 : opt[x+1][y];
                for(int k = lo;k<=hi;k++)
                    if(a.dist[x][opt[x][y]] + V[split][opt[x][y]] + b.dist[opt[x][y]][y] > a.dist[x][k] + V[split][k] + b.dist[k][y])
                        opt[x][y] = k;
            }
        }
        for(int i = 0;i<C;i++)
            for(int j = 0;j<C;j++)
                c.dist[i][j] = a.dist[i][opt[i][j]] + V[split][opt[i][j]] + b.dist[opt[i][j]][j];
        return c;
    }
} tree[4*(5000/BSZ + 7)];
void build(int ind , int l , int r){
    // cout << "build : " << ind << " " << l << " " << r << endl;
    if(l == r){
        tree[ind].update(l * BSZ , min(R,(l+1)*BSZ)-1);
        // cout << "block : " << l << endl;
        // for(int i = 0;i<C;i++){
        //     for(int j = 0;j<C;j++){
        //         cout << tree[ind].dist[i][j] << " ";
        //     }
        //     cout << endl;
        // }
        // cout << endl;
        return;
    }
    int mid = (l + r) / 2;
    build(ind*2,l,mid);
    build(ind*2+1,mid+1,r);
    tree[ind] = merge(tree[ind*2] , tree[ind*2+1] , (mid+1)*BSZ-1);
    // cout << l << " " << r << " : " << (mid+1)*BSZ-1 << endl;
}
void update(int pos , int ind , int l , int r){
    if(l == r){
        tree[ind].update(l * BSZ , min(R,(l+1)*BSZ)-1);
        return;
    }
    int mid = (l + r) / 2;
    if(pos <= mid)update(pos,ind*2,l,mid);
    else update(pos,ind*2+1,mid+1,r);
    tree[ind] = merge(tree[ind*2] , tree[ind*2+1] , (mid+1)*BSZ-1);
}
void init(int iR, int iC, int iH[5000][200], int iV[5000][200]) {
    // cout << "flag0" << endl;
    R = iR , C = iC;
    for(int i = 0;i<5000;i++){
        for(int j = 0;j<200;j++){
            H[i][j] = iH[i][j];
            V[i][j] = iV[i][j];
        }
    }
    // cout << "flag1" << endl;
    build(1,0,(R+BSZ-1)/BSZ-1);
}
void changeH(int P, int Q, int W) {
    H[P][Q] = W;
    update(P/BSZ , 1 , 0 , (R+BSZ-1)/BSZ-1);
}

void changeV(int P, int Q, int W) {
    V[P][Q] = W;
    update(P/BSZ , 1 , 0 , (R+BSZ-1)/BSZ-1);
}

int escape(int V1, int V2) {
    return tree[1].dist[V1][V2];
}

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