oj.uz

답안 #935088

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
935088 2024-02-28T15:17:04 Z anton 웜뱃 (IOI13_wombats) C++17
55 / 100
 20000 ms 123320 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 = 2;

Mat tr1[5010/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

# 결과 실행 시간 메모리 Grader output
1 Correct 5880 ms 119640 KB Output is correct
2 Correct 5836 ms 119632 KB Output is correct
3 Correct 5894 ms 121680 KB Output is correct
4 Correct 5840 ms 119640 KB Output is correct
5 Correct 5830 ms 120000 KB Output is correct
6 Correct 22 ms 103004 KB Output is correct
7 Correct 22 ms 102924 KB Output is correct
8 Correct 23 ms 103004 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 102996 KB Output is correct
2 Correct 22 ms 103004 KB Output is correct
3 Correct 22 ms 102996 KB Output is correct
4 Correct 25 ms 105044 KB Output is correct
5 Correct 23 ms 105040 KB Output is correct
6 Correct 23 ms 105040 KB Output is correct
7 Correct 24 ms 105044 KB Output is correct
8 Correct 27 ms 105208 KB Output is correct
9 Correct 24 ms 104980 KB Output is correct
10 Correct 24 ms 105040 KB Output is correct
11 Correct 78 ms 106064 KB Output is correct
12 Correct 24 ms 105040 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 915 ms 105296 KB Output is correct
2 Correct 3002 ms 105300 KB Output is correct
3 Correct 3227 ms 105224 KB Output is correct
4 Correct 3328 ms 105220 KB Output is correct
5 Correct 3187 ms 105212 KB Output is correct
6 Correct 23 ms 102996 KB Output is correct
7 Correct 21 ms 102996 KB Output is correct
8 Correct 22 ms 103004 KB Output is correct
9 Correct 4692 ms 105232 KB Output is correct
10 Correct 23 ms 105048 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5918 ms 122052 KB Output is correct
2 Correct 5868 ms 122196 KB Output is correct
3 Correct 5931 ms 122056 KB Output is correct
4 Correct 5908 ms 123320 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 923 ms 105300 KB Output is correct
2 Correct 3008 ms 105300 KB Output is correct
3 Correct 3255 ms 105400 KB Output is correct
4 Correct 3306 ms 105220 KB Output is correct
5 Correct 3165 ms 105220 KB Output is correct
6 Correct 5887 ms 122060 KB Output is correct
7 Correct 5917 ms 122060 KB Output is correct
8 Correct 5867 ms 122056 KB Output is correct
9 Correct 5967 ms 122840 KB Output is correct
10 Correct 5831 ms 120000 KB Output is correct
11 Correct 5880 ms 119996 KB Output is correct
12 Correct 5854 ms 121536 KB Output is correct
13 Correct 5804 ms 119996 KB Output is correct
14 Correct 5792 ms 120000 KB Output is correct
15 Correct 26 ms 103000 KB Output is correct
16 Correct 23 ms 103004 KB Output is correct
17 Correct 22 ms 102964 KB Output is correct
18 Correct 25 ms 105052 KB Output is correct
19 Correct 24 ms 105052 KB Output is correct
20 Correct 23 ms 105040 KB Output is correct
21 Correct 25 ms 105024 KB Output is correct
22 Correct 24 ms 105044 KB Output is correct
23 Correct 25 ms 105052 KB Output is correct
24 Correct 23 ms 104964 KB Output is correct
25 Correct 80 ms 106068 KB Output is correct
26 Correct 25 ms 105052 KB Output is correct
27 Correct 4660 ms 105228 KB Output is correct
28 Execution timed out 20098 ms 121936 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 931 ms 105396 KB Output is correct
2 Correct 3018 ms 105224 KB Output is correct
3 Correct 3237 ms 105216 KB Output is correct
4 Correct 3296 ms 105220 KB Output is correct
5 Correct 3189 ms 105224 KB Output is correct
6 Correct 5845 ms 122312 KB Output is correct
7 Correct 5827 ms 122308 KB Output is correct
8 Correct 5871 ms 122312 KB Output is correct
9 Correct 5919 ms 123036 KB Output is correct
10 Correct 5818 ms 119996 KB Output is correct
11 Correct 5848 ms 119996 KB Output is correct
12 Correct 5908 ms 121536 KB Output is correct
13 Correct 5912 ms 120148 KB Output is correct
14 Correct 5842 ms 120000 KB Output is correct
15 Execution timed out 20030 ms 121936 KB Time limit exceeded
16 Halted 0 ms 0 KB -