Submission #1162460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162460		ty_mxzhn	Wombats (IOI13_wombats)	C++20	39 / 100	20073 ms	17244 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;
int r,c,h[5000][200],v[5000][200];
int ans[200][200];
vector<vector<int>> dijkstra_up(int x , int y){
    vector vis(r , vector < int > (c , inf));
    priority_queue<array<int,3>> pq;
    pq.push({0,x,y});
    while(!pq.empty()){
        auto tmp = pq.top();
        pq.pop();
        if(vis[tmp[1]][tmp[2]] != inf)continue;
        vis[tmp[1]][tmp[2]] = -tmp[0];
        if(tmp[2] > 0)pq.push({tmp[0] - h[tmp[1]][tmp[2]-1],tmp[1],tmp[2]-1});
        if(tmp[2] < c-1)pq.push({tmp[0] - h[tmp[1]][tmp[2]],tmp[1],tmp[2]+1});
        if(tmp[1] > 0)pq.push({tmp[0] - v[tmp[1]-1][tmp[2]],tmp[1]-1,tmp[2]});
    }
    return vis;
}
vector<vector<int>> dijkstra_down(int x , int y){
    // cout << "dijkstra_down : " << x << " " << y << endl;
    vector vis(r , vector < int > (c , inf));
    priority_queue<array<int,3>> pq;
    pq.push({0,x,y});
    // cout << "starting" << endl;
    while(!pq.empty()){
        auto tmp = pq.top();
        pq.pop();
        // cout << "ok ? " << tmp[0] << " " << tmp[1] << " " << tmp[2] << endl;
        if(vis[tmp[1]][tmp[2]] != inf)continue;
        vis[tmp[1]][tmp[2]] = -tmp[0];
        if(tmp[2] > 0)pq.push({tmp[0] - h[tmp[1]][tmp[2]-1],tmp[1],tmp[2]-1});
        if(tmp[2] < c-1)pq.push({tmp[0] - h[tmp[1]][tmp[2]],tmp[1],tmp[2]+1});
        if(tmp[1] < r-1)pq.push({tmp[0] - v[tmp[1]][tmp[2]],tmp[1]+1,tmp[2]});
    }
    // cout << "done" << endl;
    return vis;
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    // cout << "flag0" << endl;
    for(int i = 0;i<200;i++){
        for(int j = 0;j<200;j++){
            ans[i][j] = inf;
        }
    }
    r = R , c = C;
    // cout << "flag1" << endl;
    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];
        }
    }
    // cout << "flag2" << endl;
    for(int i = 0;i<C;i++){
        auto dist = dijkstra_down(0,i);
        for(int j = 0;j<C;j++){
            ans[i][j] = min(ans[i][j] , dist[R-1][j]);
        }
    }
    // cout << "flag3" << endl;
}
void changeH(int P, int Q, int W) {
    for(int i = 0;i<200;i++){
        for(int j = 0;j<200;j++){
            ans[i][j] = inf;
        }
    }
    h[P][Q] = W;
    for(int i = 0;i<c;i++){
        auto dist = dijkstra_down(0,i);
        for(int j = 0;j<c;j++){
            ans[i][j] = min(ans[i][j] , dist[r-1][j]);
        }
    }
    // // sol yukari , sag asagi
    // auto distup = dijkstra_up(P,Q);
    // auto distdown = dijkstra_down(P,Q+1);
    // for(int i = 0;i<c;i++){
    //     for(int j = 0;j<c;j++){
    //         ans[i][j] = min(ans[i][j] , distup[0][i] + W + distdown[r-1][j]);
    //     }
    // }
    // // sol asagi , sag yukari
    // distup = dijkstra_up(P,Q+1);
    // distdown = dijkstra_down(P,Q);
    // for(int i = 0;i<c;i++){
    //     for(int j = 0;j<c;j++){
    //         ans[i][j] = min(ans[i][j] , distup[0][i] + W + distdown[r-1][j]);
    //     }
    // }
}

void changeV(int P, int Q, int W) {
    for(int i = 0;i<200;i++){
        for(int j = 0;j<200;j++){
            ans[i][j] = inf;
        }
    }
    v[P][Q] = W;
    for(int i = 0;i<c;i++){
        auto dist = dijkstra_down(0,i);
        for(int j = 0;j<c;j++){
            ans[i][j] = min(ans[i][j] , dist[r-1][j]);
        }
    }
    // // yukari yukari , asagi asagi
    // auto distup = dijkstra_up(P,Q);
    // auto distdown = dijkstra_down(P+1,Q);
    // for(int i = 0;i<c;i++){
    //     for(int j = 0;j<c;j++){
    //         ans[i][j] = min(ans[i][j] , distup[0][i] + W + distdown[r-1][j]);
    //     }
    // }
    // // yukari asagi , asagi yukari
    // distup = dijkstra_up(P+1,Q);
    // distdown = dijkstra_down(P,Q);
    // for(int i = 0;i<c;i++){
    //     for(int j = 0;j<c;j++){
    //         ans[i][j] = min(ans[i][j] , distup[0][i] + W + distdown[r-1][j]);
    //     }
    // }
}

int escape(int V1, int V2) {
    return ans[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