Submission #1162612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162612		ty_mxzhn	Wombats (IOI13_wombats)	C++20	39 / 100	20090 ms	47208 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 = 50;
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] = inf;
        for(int i = 0;i<C;i++){
            // cout << "root : " << l << " , " << i << endl;
            bool vis[r-l+2][C];
            memset(vis,0,sizeof(vis));
            priority_queue < array<int,3> > pq;// dist , posx , posy
            pq.push({0,l,i});
            while(!pq.empty()){
                auto tmp = pq.top();  
                pq.pop();  
                if(vis[tmp[1]-l][tmp[2]])continue;
                // cout << tmp[1] << " " << tmp[2] << " : " << -tmp[0] << endl;
                vis[tmp[1]-l][tmp[2]] = 1;
                if(tmp[1] == r)
                    dist[i][tmp[2]] = min(dist[i][tmp[2]] , -tmp[0]);
                if(tmp[1] < r and !vis[tmp[1]+1-l][tmp[2]])// asagi
                    pq.push({tmp[0] - V[tmp[1]][tmp[2]] , tmp[1]+1 , tmp[2]});
                if(tmp[2] < C-1 and !vis[tmp[1]-l][tmp[2]+1])// saga
                    pq.push({tmp[0] - H[tmp[1]][tmp[2]] , tmp[1] , tmp[2]+1});
                if(tmp[2] > 0 and !vis[tmp[1]-l][tmp[2]-1])// sola
                    pq.push({tmp[0] - H[tmp[1]][tmp[2]-1] , tmp[1] , tmp[2]-1});
            }
        }
    }
    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: 0 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24