oj.uz

Submission #1074073

# Submission time Handle Problem Language Result Execution time Memory
1074073 2024-08-25T07:37:25 Z mindiyak Wombats (IOI13_wombats) C++14
37 / 100
 20000 ms 24604 KB 
#include "wombats.h"
#include <vector>
#include <iostream>
#include <queue>

typedef long long ll;
#define F first
#define S second

using namespace std;

int H[5000][200];
int V[5000][200];
int R,C; 
int sum = 0;
int sub2 = 0;
int dp[25][25];

void calc2(int V1){
    priority_queue<pair<int,pair<int,int>>> pq;

    pq.push({0,{0,V1}});
    int dis[25][25];
    int vis[25][25];

    for(int i=0;i<25;i++)for(int j=0;j<25;j++)dis[i][j] = 2e9;
    for(int i=0;i<25;i++)for(int j=0;j<25;j++)vis[i][j] = 0;

    dis[0][V1] = 0;

    while(!pq.empty()){
        int y = pq.top().S.F;
        int x = pq.top().S.S;
        pq.pop();

        if(vis[y][x])continue;
        vis[y][x] = 1;

        if(x > 0 && (dis[y][x] + H[y][x-1] < dis[y][x-1])){
            // cerr << x << "," << y << " " << dis[y][x] << " " << H[y][x-1] << " L\n";
            dis[y][x-1] = dis[y][x] + H[y][x-1];
            pq.push({-dis[y][x-1],{y,x-1}});
        }

        if(x < (C-1) && (dis[y][x] + H[y][x] < dis[y][x+1])){
            // cerr << x << "," << y << " " << dis[y][x] << " " << H[y][x] << " R\n";
            dis[y][x+1] = dis[y][x] + H[y][x];
            pq.push({-dis[y][x+1],{y,x+1}});
        }

        if(y < (R-1) && (dis[y][x] + V[y][x] < dis[y+1][x])){
            // cerr << x << "," << y << " " << dis[y][x] << " " << V[y][x] << " D\n";
            dis[y+1][x] = dis[y][x] + V[y][x];
            pq.push({-dis[y+1][x],{y+1,x}});
        }
    }

    // for(int i=0;i<R;i++){
    //     for(int j=0;j<C;j++){
    //         cerr << dis[i][j] << " ";
    //     }cerr << endl;
    // }cerr << endl;

    for(int i=0;i<25;i++)dp[V1][i] = dis[R-1][i];
}

void init(int r, int c, int h[5000][200], int v[5000][200]) {
    R = r;
    C = c;
    if(R<=20 && C<= 20)sub2 = 1;
    for(int i=0;i<5000;i++)for(int j=0;j<200;j++)H[i][j] = h[i][j];
    for(int i=0;i<5000;i++)for(int j=0;j<200;j++)V[i][j] = v[i][j];
    for(int i=0;i<5000;i++)for(int j=0;j<200;j++)sum += V[i][j];

    if(sub2){
        for(int i=0;i<25;i++)calc2(i);
    }   
}

void changeH(int P, int Q, int W) {
    H[P][Q] = W;
    sub2 = 0;
}

void changeV(int P, int Q, int W) {
    sum -= V[P][Q];
    sum += W;
    V[P][Q] = W;
    sub2 = 0;
}

int escape(int V1, int V2) {
    if(C == 1){
        return sum;
    }
    if(sub2){
        return dp[V1][V2];
    }
    priority_queue<pair<int,pair<int,int>>> pq;

    pq.push({0,{0,V1}});
    int dis[5005][205];
    int vis[5005][205];

    for(int i=0;i<5005;i++)for(int j=0;j<205;j++)dis[i][j] = 2e9;
    for(int i=0;i<5005;i++)for(int j=0;j<205;j++)vis[i][j] = 0;

    dis[0][V1] = 0;

    while(!pq.empty()){
        int y = pq.top().S.F;
        int x = pq.top().S.S;
        pq.pop();

        if(vis[y][x])continue;
        vis[y][x] = 1;

        if(x > 0 && (dis[y][x] + H[y][x-1] < dis[y][x-1])){
            // cerr << x << "," << y << " " << dis[y][x] << " " << H[y][x-1] << " L\n";
            dis[y][x-1] = dis[y][x] + H[y][x-1];
            pq.push({-dis[y][x-1],{y,x-1}});
        }

        if(x < (C-1) && (dis[y][x] + H[y][x] < dis[y][x+1])){
            // cerr << x << "," << y << " " << dis[y][x] << " " << H[y][x] << " R\n";
            dis[y][x+1] = dis[y][x] + H[y][x];
            pq.push({-dis[y][x+1],{y,x+1}});
        }

        if(y < (R-1) && (dis[y][x] + V[y][x] < dis[y+1][x])){
            // cerr << x << "," << y << " " << dis[y][x] << " " << V[y][x] << " D\n";
            dis[y+1][x] = dis[y][x] + V[y][x];
            pq.push({-dis[y+1][x],{y+1,x}});
        }
    }

    // for(int i=0;i<R;i++){
    //     for(int j=0;j<C;j++){
    //         cerr << dis[i][j] << " ";
    //     }cerr << endl;
    // }cerr << endl;

    return dis[R-1][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 29 ms 20060 KB Output is correct
2 Correct 29 ms 20060 KB Output is correct
3 Correct 5665 ms 22972 KB Output is correct
4 Correct 30 ms 20060 KB Output is correct
5 Correct 25 ms 20060 KB Output is correct
6 Correct 9 ms 16220 KB Output is correct
7 Correct 15 ms 16220 KB Output is correct
8 Correct 10 ms 16136 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16220 KB Output is correct
2 Correct 9 ms 16220 KB Output is correct
3 Correct 9 ms 16216 KB Output is correct
4 Correct 18 ms 16220 KB Output is correct
5 Correct 22 ms 16220 KB Output is correct
6 Correct 25 ms 16220 KB Output is correct
7 Correct 23 ms 16220 KB Output is correct
8 Correct 26 ms 16216 KB Output is correct
9 Correct 29 ms 16260 KB Output is correct
10 Correct 20 ms 16220 KB Output is correct
11 Correct 6277 ms 18508 KB Output is correct
12 Correct 20 ms 16348 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 16472 KB Output is correct
2 Correct 225 ms 16696 KB Output is correct
3 Correct 166 ms 16540 KB Output is correct
4 Correct 162 ms 16476 KB Output is correct
5 Correct 162 ms 16476 KB Output is correct
6 Correct 10 ms 16220 KB Output is correct
7 Correct 11 ms 16128 KB Output is correct
8 Correct 9 ms 16220 KB Output is correct
9 Correct 234 ms 16472 KB Output is correct
10 Correct 15 ms 16220 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 905 ms 24164 KB Output is correct
2 Correct 1403 ms 24168 KB Output is correct
3 Correct 888 ms 24152 KB Output is correct
4 Execution timed out 20073 ms 24604 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 16472 KB Output is correct
2 Correct 214 ms 16672 KB Output is correct
3 Correct 155 ms 16472 KB Output is correct
4 Correct 152 ms 16472 KB Output is correct
5 Correct 154 ms 16476 KB Output is correct
6 Correct 832 ms 24152 KB Output is correct
7 Correct 1329 ms 24144 KB Output is correct
8 Correct 838 ms 24156 KB Output is correct
9 Execution timed out 20010 ms 24596 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 16476 KB Output is correct
2 Correct 216 ms 16672 KB Output is correct
3 Correct 156 ms 16476 KB Output is correct
4 Correct 156 ms 16472 KB Output is correct
5 Correct 159 ms 16360 KB Output is correct
6 Correct 825 ms 24156 KB Output is correct
7 Correct 1334 ms 24156 KB Output is correct
8 Correct 856 ms 24156 KB Output is correct
9 Execution timed out 20049 ms 24104 KB Time limit exceeded
10 Halted 0 ms 0 KB -