oj.uz

Submission #935081

# Submission time Handle Problem Language Result Execution time Memory
935081 2024-02-28T15:08:46 Z anton Wombats (IOI13_wombats) C++17
39 / 100
 20000 ms 44404 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];

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];
            }
        }
    }
    find_global();
}

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];
        }
    }
    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 602 ms 32740 KB Output is correct
2 Correct 592 ms 32744 KB Output is correct
3 Correct 658 ms 35384 KB Output is correct
4 Correct 599 ms 32856 KB Output is correct
5 Correct 657 ms 32672 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 4 ms 14684 KB Output is correct
8 Correct 5 ms 14684 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3527 ms 21172 KB Output is correct
2 Correct 5266 ms 21208 KB Output is correct
3 Correct 3697 ms 21332 KB Output is correct
4 Correct 3629 ms 21172 KB Output is correct
5 Correct 3718 ms 21176 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14808 KB Output is correct
8 Correct 3 ms 14936 KB Output is correct
9 Execution timed out 20093 ms 21208 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 34848 KB Output is correct
2 Correct 611 ms 34836 KB Output is correct
3 Correct 618 ms 34652 KB Output is correct
4 Correct 635 ms 36056 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3502 ms 21180 KB Output is correct
2 Correct 5309 ms 21200 KB Output is correct
3 Correct 3803 ms 21096 KB Output is correct
4 Correct 3795 ms 21168 KB Output is correct
5 Correct 3754 ms 21168 KB Output is correct
6 Correct 609 ms 35084 KB Output is correct
7 Correct 603 ms 34824 KB Output is correct
8 Correct 607 ms 34848 KB Output is correct
9 Correct 649 ms 36220 KB Output is correct
10 Correct 594 ms 32760 KB Output is correct
11 Correct 612 ms 32772 KB Output is correct
12 Correct 655 ms 35392 KB Output is correct
13 Correct 594 ms 32856 KB Output is correct
14 Correct 600 ms 32748 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Correct 4 ms 14804 KB Output is correct
17 Correct 4 ms 14776 KB Output is correct
18 Correct 5 ms 18776 KB Output is correct
19 Correct 5 ms 18780 KB Output is correct
20 Correct 5 ms 18884 KB Output is correct
21 Correct 6 ms 18984 KB Output is correct
22 Correct 5 ms 18780 KB Output is correct
23 Correct 7 ms 18924 KB Output is correct
24 Correct 5 ms 18780 KB Output is correct
25 Correct 60 ms 21100 KB Output is correct
26 Correct 5 ms 18776 KB Output is correct
27 Execution timed out 20052 ms 21328 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3544 ms 21172 KB Output is correct
2 Correct 5099 ms 21204 KB Output is correct
3 Correct 3764 ms 21176 KB Output is correct
4 Correct 3677 ms 21176 KB Output is correct
5 Correct 3827 ms 21176 KB Output is correct
6 Correct 629 ms 34844 KB Output is correct
7 Correct 640 ms 34904 KB Output is correct
8 Correct 687 ms 34848 KB Output is correct
9 Correct 670 ms 36016 KB Output is correct
10 Correct 663 ms 32604 KB Output is correct
11 Correct 622 ms 32744 KB Output is correct
12 Correct 689 ms 35412 KB Output is correct
13 Correct 603 ms 32748 KB Output is correct
14 Correct 609 ms 32744 KB Output is correct
15 Execution timed out 20057 ms 44404 KB Time limit exceeded
16 Halted 0 ms 0 KB -