oj.uz

Submission #935079

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

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 = 100;

Mat tr1[6000/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 445 ms 31708 KB Output is correct
2 Correct 484 ms 31828 KB Output is correct
3 Correct 495 ms 33104 KB Output is correct
4 Correct 453 ms 31700 KB Output is correct
5 Correct 468 ms 31576 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 3 ms 15064 KB Output is correct
8 Correct 3 ms 15028 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14940 KB Output is correct
2 Correct 4 ms 15056 KB Output is correct
3 Correct 3 ms 14940 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 4 ms 17096 KB Output is correct
6 Correct 4 ms 16988 KB Output is correct
7 Correct 5 ms 16988 KB Output is correct
8 Correct 5 ms 16988 KB Output is correct
9 Correct 5 ms 16988 KB Output is correct
10 Correct 4 ms 16988 KB Output is correct
11 Correct 59 ms 18140 KB Output is correct
12 Correct 5 ms 16984 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 17497 ms 17232 KB Output is correct
2 Execution timed out 20034 ms 17596 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 33980 KB Output is correct
2 Correct 481 ms 33760 KB Output is correct
3 Correct 500 ms 33764 KB Output is correct
4 Correct 507 ms 34320 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 17109 ms 17228 KB Output is correct
2 Execution timed out 20025 ms 18080 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17387 ms 17232 KB Output is correct
2 Execution timed out 20091 ms 17828 KB Time limit exceeded
3 Halted 0 ms 0 KB -