Submission #1140874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140874		urosk	Wombats (IOI13_wombats)	C++20	39 / 100	20088 ms	220204 KiB

wombats

#include "wombats.h"
#include "bits/stdc++.h"
#define here cerr<<"=======================================\n"
using ll = int;

using namespace std;
const ll maxn = 10005;
const ll maxh = 205;
const ll llinf = 2000000000;
ll n,m;
ll t[maxh][maxh][maxn], ls[maxn],rs[maxn];
ll a[maxn][maxh];
ll b[maxn][maxh];
ll tsz = 0,root = 0;
ll ps[maxh];
void iit(ll &v,ll tl,ll tr) {
    if(!v) v = ++tsz;
    if(tl==tr) {
        for(ll i = 2;i<=m;i++) ps[i] = ps[i-1] + a[tl][i-1];
        for(ll i = 1;i<=m;i++) {
            for(ll j = 1;j<=m;j++) t[i][j][v] = ps[max(i,j)]-ps[min(i,j)];
        }
        return;
    }
    ll mid = (tl+tr)/2;
    iit(ls[v],tl,mid);
    iit(rs[v],mid+1,tr);
    for(ll i = 1;i<=m;i++) {
        for(ll j = 1;j<=m;j++) {
            t[i][j][v] = llinf;
            for(ll k = 1;k<=m;k++) t[i][j][v] = min(t[i][j][v],t[i][k][ls[v]]+t[k][j][rs[v]]+b[mid][k]);
        }
    }
}
void upd(ll v,ll tl,ll tr,ll id) {
    if(tl==tr) {
        for(ll i = 2;i<=m;i++) ps[i] = ps[i-1] + a[tl][i-1];
        for(ll i = 1;i<=m;i++) {
            for(ll j = 1;j<=m;j++) t[i][j][v] = ps[max(i,j)]-ps[min(i,j)];
        }
        return;
    }
    ll mid = (tl+tr)/2;
    if(id<=mid) upd(ls[v],tl,mid,id);
    else upd(rs[v],mid+1,tr,id);
    for(ll i = 1;i<=m;i++) {
        for(ll j = 1;j<=m;j++) {
            t[i][j][v] = llinf;
            for(ll k = 1;k<=m;k++) t[i][j][v] = min(t[i][j][v],t[i][k][ls[v]]+t[k][j][rs[v]]+b[mid][k]);
        }
    }
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n = R,m = C;
    for(ll i = 1;i<=n;i++) {
        for(ll j = 1;j<=m;j++) a[i][j] = H[i-1][j-1],b[i][j] = V[i-1][j-1];
    }
    iit(root,1,n);
}

void changeH(int P, int Q, int W) {
    ll x = P+1,y = Q+1,w = W;
    a[x][y] = w;
    upd(root,1,n,x);
}

void changeV(int P, int Q, int W) {
    ll x = P+1,y = Q+1,w = W;
    b[x][y] = w;
    upd(root,1,n,x);
    if(x>1) upd(root,1,n,x-1);
    else if(x<n) upd(root,1,n,x+1);
}

int escape(int V1, int V2) {
    V1++,V2++;
    return t[V1][V2][root];
}

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