oj.uz

Submission #935077

# Submission time Handle Problem Language Result Execution time Memory
935077 2024-02-28T14:55:17 Z anton Wombats (IOI13_wombats) C++17
39 / 100
 622 ms 32760 KB 
#include "wombats.h"
#include<bits/stdc++.h>

using namespace std;
#define pii pair<int, int>

int tr[5000][200][3];
int delta[3][2] = {{0, 1}, {0, -1}, {1, 0}};
int dist[5000][200];

const int MAT_SZ= 20;

struct Mat{
    int dt[MAT_SZ][MAT_SZ];
    Mat(){
        for(int i = 0; i<MAT_SZ; i++){
            for(int j = 0; j<MAT_SZ; j++){
                dt[i][j] = 1e9;
            }
        }
    }
};

int r, c;

Mat e(){
    Mat res;
    for(int i = 0; i<MAT_SZ; i++){
        res.dt[i][i] = 0;
    }
    return res;
}

Mat compose(Mat& a, Mat& b){
    Mat res= Mat();
    for(int i = 0; i<c; i++){
        for(int j= 0; j<c; j++){
            for(int k = 0; k<c; k++){
                res.dt[i][k] = min(res.dt[i][k], a.dt[i][j] + b.dt[j][k]);
            }
        }
    }
    return res;
}

Mat tr1[5000];

Mat global;
 
vector<pair<pii, int>> gen_adj(pii pos){
    vector<pair<pii, int>> res;
    for(int trid = 0; trid<3; trid++){
        pii potential = {pos.first + delta[trid][0], pos.second + delta[trid][1]};
        if(potential.first<r && potential.second>=0 && potential.second<c){
            res.push_back({potential, tr[pos.first][pos.second][trid]});
        }
    }
    return res;
}

int dijkstra(pii begin, pii dest){
 
    for(int i = 0; i<r; i++){
        for(int j = 0; j<c; j++){
            dist[i][j]  = 1e9;
        }
    }
    priority_queue<pair<int, pii>> pq;
    pq.push({0, begin});
    dist[begin.first][begin.second] = 0;
 
    while(pq.size()>0){
        auto cur = pq.top();
        pq.pop();
 
 
        pii pos=  cur.second;
        int d = -cur.first;
        //cout<<pos.first<<" "<<pos.second<<" "<<d<<endl;
        if(d== dist[pos.first][pos.second]){
            auto adj = gen_adj(pos);
            for(auto e: adj){

                if(e.first.first<= dest.first && d + e.second< dist[e.first.first][e.first.second]){
                    dist[e.first.first][e.first.second]= d + e.second;
                    pq.push({-d-e.second, e.first});
                }
            }
        }
    }
    return dist[dest.first][dest.second];
}

void find_global(){
    Mat cur = e();
    for(int i = 0; i<r-1; i++){
        cur = compose(cur, tr1[i]);
    }
    global =cur;
}
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r= R;
    c= C;
    for(int p = 0; p<R; p++){
        for(int q=  0; q<C-1; q++){
            tr[p][q][0] = H[p][q];
            tr[p][q+1][1] = H[p][q];
        }
        if(p<R-1){
            for(int q=  0; q<C; q++){
                tr[p][q][2] = V[p][q];
            }
        }
    }

    for(int p = 0; p<R-1; p++){
        for(int q=  0; q<C; q++){
            dijkstra({p, q}, {p+1, q});

            for(int qt=  0; qt<C; qt++){
                tr1[p].dt[q][qt] = dist[p+1][qt];
            }
        }
    }
    find_global();
}



void changeH(int P, int Q, int W) {
    tr[P][Q][0] = W;
    tr[P][Q+1][1] = W;
    for(int p = max(0, P-1); p<=min(P, r-2); p++){
        for(int q=  0; q<c; q++){
            dijkstra({p, q}, {p+1, q});
            for(int qt=  0; qt<c; qt++){
                tr1[p].dt[q][qt] = dist[p+1][qt];
            }
        }
    }
    find_global();
}

void changeV(int P, int Q, int W) {
    tr[P][Q][2] = W;
    for(int q=  0; q<c; q++){
        dijkstra({P, q}, {P+1, q});
        for(int qt=  0; qt<c; qt++){
            tr1[P].dt[q][qt] = dist[P+1][qt];
        }
    }
    find_global();
}



int escape(int V1, int V2) {
    return global.dt[V1][V2];
}

Compilation message

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 29680 KB Output is correct
2 Correct 533 ms 29776 KB Output is correct
3 Correct 584 ms 31484 KB Output is correct
4 Correct 536 ms 29704 KB Output is correct
5 Correct 524 ms 29700 KB Output is correct
6 Correct 3 ms 12632 KB Output is correct
7 Correct 3 ms 12632 KB Output is correct
8 Correct 2 ms 12736 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 2 ms 12632 KB Output is correct
4 Correct 5 ms 14684 KB Output is correct
5 Correct 4 ms 14684 KB Output is correct
6 Correct 5 ms 14776 KB Output is correct
7 Correct 5 ms 14684 KB Output is correct
8 Correct 4 ms 14776 KB Output is correct
9 Correct 5 ms 14680 KB Output is correct
10 Correct 5 ms 14684 KB Output is correct
11 Correct 60 ms 15612 KB Output is correct
12 Correct 5 ms 14684 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 255 ms 29704 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 31716 KB Output is correct
2 Correct 595 ms 31580 KB Output is correct
3 Correct 583 ms 31824 KB Output is correct
4 Correct 622 ms 32760 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 242 ms 29700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 248 ms 29700 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -