oj.uz

Submission #358275

# Submission time Handle Problem Language Result Execution time Memory
358275 2021-01-25T09:27:42 Z beksultan04 Wombats (IOI13_wombats) C++14
28 / 100
 20000 ms 20448 KB 
#include "wombats.h"
#ifndef EVAL
#include "grader.c"
#endif // EVAL
#include <bits/stdc++.h>
using namespace std;
#define lol long long
#define pii pair<int,int>
#define OK puts("OK");
#define NO puts("NO");
#define YES puts("YES");
#define fr first
#define sc second
#define ret return
#define scanl(a) scanf("%lld",&a);
#define scanll(a,b) scanf("%lld %lld",&a, &b);
#define scanlll(a,b,c) scanf("%lld %lld %lld",&a,&b,&c);
#define scan1(a) scanf("%d",&a);
#define scan2(a,b) scanf("%d %d",&a, &b);
#define scan3(a,b,c) scanf("%d %d %d",&a,&b,&c);
#define all(s) s.begin(),s.end()
#define allr(s) s.rbegin(),s.rend()
#define pb push_back
#define sz(v) (int)v.size()
#define endi puts("");
#define INF 1e9+7

int r[5000][200],d[5000][200],cost[5000][200],R,C;

void init(int R, int C, int H[5000][200], int V[5000][200]){
    ::R = R;
    ::C = C;

    for (int i=0;i<R;++i)
        for (int j=0;j<C;++j){
            cost[i][j] = INF;
            r[i][j] = H[i][j];
            d[i][j] = V[i][j];
        }
    /* ... */
}

void changeH(int P, int Q, int W) {
    r[P][Q] = W;
    /* ... */
}

void changeV(int P, int Q, int W) {
    d[P][Q] = W;
    /* ... */
}

int escape(int V1, int V2) {

    for (int i=0;i<R;++i)
        for (int j=0;j<C;++j)
            cost[i][j] = INF;


    set <pair<lol,pii> > s;
    s.insert({0,{0,V1}});
    cost[0][V1] = 0;
    while (!s.empty()){
        pii p = s.begin()->sc;
        s.erase(s.begin());
        if (p.fr+1 < R){
            if (cost[p.fr+1][p.sc] > cost[p.fr][p.sc]+d[p.fr][p.sc]){

                s.erase({cost[p.fr+1][p.sc],{p.fr+1,p.sc}});
                cost[p.fr+1][p.sc] = cost[p.fr][p.sc]+d[p.fr][p.sc];
                s.insert({cost[p.fr+1][p.sc],{p.fr+1,p.sc}});

            }
        }
        if (p.sc+1 < C){
            if (cost[p.fr][p.sc+1] > cost[p.fr][p.sc]+r[p.fr][p.sc]){

                s.erase({cost[p.fr][p.sc+1],{p.fr,p.sc+1}});
                cost[p.fr][p.sc+1] = cost[p.fr][p.sc]+r[p.fr][p.sc];
                s.insert({cost[p.fr][p.sc+1],{p.fr,p.sc+1}});

            }
        }
        if (p.sc-1 >= 0){
            if (cost[p.fr][p.sc-1] > cost[p.fr][p.sc]+r[p.fr][p.sc-1]){

                s.erase({cost[p.fr][p.sc-1],{p.fr,p.sc-1}});
                cost[p.fr][p.sc-1] = cost[p.fr][p.sc]+r[p.fr][p.sc-1];
                s.insert({cost[p.fr][p.sc-1],{p.fr,p.sc-1}});

            }
        }

    }


    return cost[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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 16040 KB Output is correct
2 Correct 136 ms 15980 KB Output is correct
3 Execution timed out 20067 ms 16596 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 33 ms 364 KB Output is correct
5 Correct 18 ms 364 KB Output is correct
6 Correct 19 ms 364 KB Output is correct
7 Correct 32 ms 384 KB Output is correct
8 Correct 27 ms 492 KB Output is correct
9 Correct 31 ms 624 KB Output is correct
10 Correct 30 ms 512 KB Output is correct
11 Correct 15765 ms 1736 KB Output is correct
12 Correct 40 ms 364 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 896 KB Output is correct
2 Correct 319 ms 876 KB Output is correct
3 Correct 298 ms 812 KB Output is correct
4 Correct 257 ms 876 KB Output is correct
5 Correct 296 ms 876 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 261 ms 748 KB Output is correct
10 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 993 ms 19948 KB Output is correct
2 Correct 915 ms 19948 KB Output is correct
3 Correct 1006 ms 20076 KB Output is correct
4 Execution timed out 20066 ms 20076 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 748 KB Output is correct
2 Correct 334 ms 876 KB Output is correct
3 Correct 271 ms 876 KB Output is correct
4 Correct 254 ms 748 KB Output is correct
5 Correct 259 ms 876 KB Output is correct
6 Correct 1002 ms 20072 KB Output is correct
7 Correct 903 ms 19948 KB Output is correct
8 Correct 983 ms 20072 KB Output is correct
9 Execution timed out 20037 ms 20096 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 748 KB Output is correct
2 Correct 305 ms 876 KB Output is correct
3 Correct 258 ms 876 KB Output is correct
4 Correct 256 ms 876 KB Output is correct
5 Correct 260 ms 748 KB Output is correct
6 Correct 1022 ms 19948 KB Output is correct
7 Correct 914 ms 19948 KB Output is correct
8 Correct 998 ms 20116 KB Output is correct
9 Execution timed out 20035 ms 20448 KB Time limit exceeded
10 Halted 0 ms 0 KB -