oj.uz

답안 #935086

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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 2354 ms 65012 KB Output is correct
2 Correct 2351 ms 65000 KB Output is correct
3 Correct 2419 ms 66440 KB Output is correct
4 Correct 2338 ms 65016 KB Output is correct
5 Correct 2358 ms 65008 KB Output is correct
6 Correct 11 ms 47708 KB Output is correct
7 Correct 11 ms 47708 KB Output is correct
8 Correct 11 ms 47576 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 47708 KB Output is correct
2 Correct 10 ms 47600 KB Output is correct
3 Correct 11 ms 47704 KB Output is correct
4 Correct 12 ms 49756 KB Output is correct
5 Correct 12 ms 49756 KB Output is correct
6 Correct 12 ms 49656 KB Output is correct
7 Correct 12 ms 49756 KB Output is correct
8 Correct 15 ms 49644 KB Output is correct
9 Correct 12 ms 49752 KB Output is correct
10 Correct 12 ms 49756 KB Output is correct
11 Correct 65 ms 50516 KB Output is correct
12 Correct 12 ms 49752 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1052 ms 50004 KB Output is correct
2 Correct 2268 ms 49836 KB Output is correct
3 Correct 2069 ms 50016 KB Output is correct
4 Correct 2008 ms 50000 KB Output is correct
5 Correct 1996 ms 49824 KB Output is correct
6 Correct 11 ms 47708 KB Output is correct
7 Correct 10 ms 47544 KB Output is correct
8 Correct 12 ms 47708 KB Output is correct
9 Correct 7223 ms 49832 KB Output is correct
10 Correct 11 ms 49752 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2371 ms 67156 KB Output is correct
2 Correct 2413 ms 67060 KB Output is correct
3 Correct 2374 ms 67152 KB Output is correct
4 Correct 2426 ms 68436 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1048 ms 50004 KB Output is correct
2 Correct 2252 ms 50004 KB Output is correct
3 Correct 2093 ms 50008 KB Output is correct
4 Correct 2016 ms 50000 KB Output is correct
5 Correct 1979 ms 50000 KB Output is correct
6 Correct 2386 ms 67324 KB Output is correct
7 Correct 2392 ms 67408 KB Output is correct
8 Correct 2399 ms 67160 KB Output is correct
9 Correct 2409 ms 68044 KB Output is correct
10 Correct 2369 ms 65104 KB Output is correct
11 Correct 2375 ms 65012 KB Output is correct
12 Correct 2421 ms 66552 KB Output is correct
13 Correct 2372 ms 65016 KB Output is correct
14 Correct 2362 ms 65016 KB Output is correct
15 Correct 10 ms 47708 KB Output is correct
16 Correct 11 ms 47708 KB Output is correct
17 Correct 11 ms 47708 KB Output is correct
18 Correct 12 ms 49704 KB Output is correct
19 Correct 12 ms 49756 KB Output is correct
20 Correct 12 ms 49752 KB Output is correct
21 Correct 12 ms 49656 KB Output is correct
22 Correct 13 ms 49756 KB Output is correct
23 Correct 12 ms 49756 KB Output is correct
24 Correct 12 ms 49756 KB Output is correct
25 Correct 67 ms 50572 KB Output is correct
26 Correct 13 ms 49752 KB Output is correct
27 Correct 7146 ms 49836 KB Output is correct
28 Execution timed out 20033 ms 70436 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1049 ms 49996 KB Output is correct
2 Correct 2267 ms 49836 KB Output is correct
3 Correct 2041 ms 49820 KB Output is correct
4 Correct 2019 ms 49996 KB Output is correct
5 Correct 1982 ms 50000 KB Output is correct
6 Correct 2403 ms 67076 KB Output is correct
7 Correct 2384 ms 67072 KB Output is correct
8 Correct 2414 ms 67412 KB Output is correct
9 Correct 2397 ms 68232 KB Output is correct
10 Correct 2371 ms 65012 KB Output is correct
11 Correct 2350 ms 65012 KB Output is correct
12 Correct 2429 ms 66388 KB Output is correct
13 Correct 2373 ms 65016 KB Output is correct
14 Correct 2379 ms 65104 KB Output is correct
15 Execution timed out 20079 ms 66896 KB Time limit exceeded
16 Halted 0 ms 0 KB -