oj.uz

Submission #935084

# Submission time Handle Problem Language Result Execution time Memory
935084 2024-02-28T15:11:21 Z anton Wombats (IOI13_wombats) C++17
39 / 100
 20000 ms 35820 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= 100;

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;
}
const int SQRT = 20;

Mat tr1[5500/SQRT];

bool changed = false;
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+=SQRT){
        cur = compose(cur, tr1[i/SQRT]);
    }
    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+=SQRT){
        int end=  min(p+SQRT, r-1);
        for(int q=  0; q<C; q++){
            dijkstra({p, q}, {end, q});

            for(int qt=  0; qt<C; qt++){
                tr1[p/SQRT].dt[q][qt] = dist[end][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 = ((P-1)/SQRT)*SQRT; p<=((P)/SQRT)*SQRT; p+=SQRT){
        int end=  min(p+SQRT, r-1);
        for(int q=  0; q<c; q++){
            dijkstra({p, q}, {end, q});

            for(int qt=  0; qt<c; qt++){
                tr1[p/SQRT].dt[q][qt] = dist[end][qt];
            }
        }
    }
    changed= true;
}

void changeV(int P, int Q, int W) {
    tr[P][Q][2] = W;
    int p = ((P)/SQRT)*SQRT;
    int end=  min(p+SQRT, r-1);
    for(int q=  0; q<c; q++){
        dijkstra({p, q}, {end, q});

        for(int qt=  0; qt<c; qt++){
            tr1[p/SQRT].dt[q][qt] = dist[end][qt];
        }
    }
    changed= true;
}



int escape(int V1, int V2) {
    if(changed){
        find_global();
        changed =false;
    }
    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 587 ms 32604 KB Output is correct
2 Correct 600 ms 32732 KB Output is correct
3 Correct 642 ms 34128 KB Output is correct
4 Correct 619 ms 32736 KB Output is correct
5 Correct 592 ms 32600 KB Output is correct
6 Correct 4 ms 14684 KB Output is correct
7 Correct 3 ms 14792 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14680 KB Output is correct
4 Correct 5 ms 18776 KB Output is correct
5 Correct 4 ms 18780 KB Output is correct
6 Correct 4 ms 18780 KB Output is correct
7 Correct 5 ms 18868 KB Output is correct
8 Correct 5 ms 18776 KB Output is correct
9 Correct 5 ms 18780 KB Output is correct
10 Correct 5 ms 19032 KB Output is correct
11 Correct 60 ms 20104 KB Output is correct
12 Correct 5 ms 18780 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3203 ms 21352 KB Output is correct
2 Correct 4985 ms 21140 KB Output is correct
3 Correct 3655 ms 21332 KB Output is correct
4 Correct 3586 ms 21096 KB Output is correct
5 Correct 3609 ms 21332 KB Output is correct
6 Correct 3 ms 14680 KB Output is correct
7 Correct 4 ms 14936 KB Output is correct
8 Correct 4 ms 14684 KB Output is correct
9 Execution timed out 20007 ms 21048 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 34652 KB Output is correct
2 Correct 604 ms 34652 KB Output is correct
3 Correct 605 ms 34788 KB Output is correct
4 Correct 623 ms 35412 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3229 ms 21092 KB Output is correct
2 Correct 5120 ms 21188 KB Output is correct
3 Correct 3672 ms 21012 KB Output is correct
4 Correct 3580 ms 21096 KB Output is correct
5 Correct 3635 ms 21328 KB Output is correct
6 Correct 632 ms 34772 KB Output is correct
7 Correct 608 ms 34936 KB Output is correct
8 Correct 605 ms 34896 KB Output is correct
9 Correct 666 ms 35812 KB Output is correct
10 Correct 590 ms 32600 KB Output is correct
11 Correct 592 ms 32720 KB Output is correct
12 Correct 673 ms 34252 KB Output is correct
13 Correct 626 ms 32600 KB Output is correct
14 Correct 611 ms 32720 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 3 ms 14680 KB Output is correct
17 Correct 3 ms 14684 KB Output is correct
18 Correct 5 ms 18780 KB Output is correct
19 Correct 5 ms 18780 KB Output is correct
20 Correct 5 ms 18920 KB Output is correct
21 Correct 5 ms 18780 KB Output is correct
22 Correct 5 ms 18780 KB Output is correct
23 Correct 5 ms 18780 KB Output is correct
24 Correct 5 ms 18780 KB Output is correct
25 Correct 58 ms 19892 KB Output is correct
26 Correct 5 ms 18776 KB Output is correct
27 Execution timed out 20082 ms 21040 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3230 ms 21096 KB Output is correct
2 Correct 5000 ms 21136 KB Output is correct
3 Correct 3632 ms 21272 KB Output is correct
4 Correct 3565 ms 21332 KB Output is correct
5 Correct 3616 ms 21092 KB Output is correct
6 Correct 612 ms 34652 KB Output is correct
7 Correct 607 ms 34776 KB Output is correct
8 Correct 598 ms 34896 KB Output is correct
9 Correct 629 ms 35820 KB Output is correct
10 Correct 586 ms 32600 KB Output is correct
11 Correct 604 ms 32712 KB Output is correct
12 Correct 663 ms 34252 KB Output is correct
13 Correct 624 ms 32720 KB Output is correct
14 Correct 595 ms 32732 KB Output is correct
15 Execution timed out 20022 ms 34492 KB Time limit exceeded
16 Halted 0 ms 0 KB -