oj.uz

Submission #962231

# Submission time Handle Problem Language Result Execution time Memory
962231 2024-04-13T09:19:43 Z serkanrashid Wombats (IOI13_wombats) C++14
37 / 100
 20000 ms 21060 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

struct edge
{
    int x,y;
    long long dist;
    edge(){};
    edge(int xi, int yi, long long di)
    {
        x = xi;
        y = yi;
        dist = di;
    }
    bool operator<(const edge&ed) const
    {
        return dist>ed.dist;
    }
};

int r,c;
int h[5000][200],v[5000][200];
unsigned int d[5000][200],inf = -1;
int sum;

void changeH(int P, int Q, int W)
{
    h[P][Q] = W;
}

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

int escape(int V1, int V2)
{
    if(c==1) return sum;
    memset(d,-1,sizeof(d));
    priority_queue<edge>q;
    d[0][V1] = 0;
    q.push({0,V1,0});
    edge e,nb;
    while(!q.empty())
    {
        e = q.top();
        q.pop();
        if(e.dist<=d[e.x][e.y])
        {
            ///LEFT
            nb = {0,0,inf};
            if(e.y>0) nb = {e.x,e.y-1,h[e.x][e.y-1]};
            if(nb.dist!=inf&&e.dist+nb.dist<d[nb.x][nb.y])
            {
                nb.dist += e.dist;
                d[nb.x][nb.y] = nb.dist;
                q.push(nb);
            }

            ///RIGHT
            nb = {0,0,inf};
            if(e.y<c-1) nb = {e.x,e.y+1,h[e.x][e.y]};
            if(nb.dist!=inf&&e.dist+nb.dist<d[nb.x][nb.y])
            {
                nb.dist += e.dist;
                d[nb.x][nb.y] = nb.dist;
                q.push(nb);
            }

            ///DOWN
            nb = {0,0,inf};
            if(e.x<r-1) nb = {e.x+1,e.y,v[e.x][e.y]};
            if(nb.dist!=inf&&e.dist+nb.dist<d[nb.x][nb.y])
            {
                nb.dist += e.dist;
                d[nb.x][nb.y] = nb.dist;
                q.push(nb);
            }
        }
    }
    int pom = d[r-1][V2];
    return pom;
}

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-1;j++) h[i][j] = H[i][j];

    for(int i=0;i<R-1;i++)
        for(int j=0;j<C;j++)
        {
            v[i][j] = V[i][j];
            sum += v[i][j];
        }

}

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 3 ms 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 72 ms 13320 KB Output is correct
4 Correct 2 ms 10840 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 0 ms 2496 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 38 ms 9216 KB Output is correct
5 Correct 30 ms 9048 KB Output is correct
6 Correct 31 ms 9232 KB Output is correct
7 Correct 39 ms 9052 KB Output is correct
8 Correct 33 ms 9052 KB Output is correct
9 Correct 37 ms 9212 KB Output is correct
10 Correct 32 ms 9052 KB Output is correct
11 Correct 17256 ms 11420 KB Output is correct
12 Correct 37 ms 9052 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 9364 KB Output is correct
2 Correct 124 ms 9580 KB Output is correct
3 Correct 87 ms 9360 KB Output is correct
4 Correct 85 ms 9356 KB Output is correct
5 Correct 83 ms 9372 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 128 ms 9400 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 20056 KB Output is correct
2 Correct 899 ms 20060 KB Output is correct
3 Correct 382 ms 20060 KB Output is correct
4 Execution timed out 20101 ms 20888 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 9304 KB Output is correct
2 Correct 126 ms 9656 KB Output is correct
3 Correct 86 ms 9356 KB Output is correct
4 Correct 84 ms 9360 KB Output is correct
5 Correct 87 ms 9304 KB Output is correct
6 Correct 384 ms 20064 KB Output is correct
7 Correct 888 ms 20056 KB Output is correct
8 Correct 395 ms 20308 KB Output is correct
9 Execution timed out 20063 ms 21060 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 9360 KB Output is correct
2 Correct 120 ms 9576 KB Output is correct
3 Correct 87 ms 9308 KB Output is correct
4 Correct 85 ms 9356 KB Output is correct
5 Correct 91 ms 9480 KB Output is correct
6 Correct 380 ms 20064 KB Output is correct
7 Correct 894 ms 20060 KB Output is correct
8 Correct 375 ms 20312 KB Output is correct
9 Execution timed out 20011 ms 20796 KB Time limit exceeded
10 Halted 0 ms 0 KB -