oj.uz

Submission #207268

# Submission time Handle Problem Language Result Execution time Memory
207268 2020-03-06T21:00:20 Z oko Wombats (IOI13_wombats) C++14
21 / 100
 20000 ms 55544 KB 
#include<bits/stdc++.h>
#include "wombats.h"
using namespace std;
long long n,m,h[5005][205],v[5005][205],dis[5005][205][205],xx[]= {-1,0,0},yy[]= {0,-1,1},on[205];

void dij(int i)
{
    priority_queue<pair<long long,pair<int,int> > >q;
    for(int j=0; j<n; j++)
    {
        for(int z=0; z<m; z++)dis[j][z][i]=1e18;
    }
    dis[n-1][i][i]=0;
    q.push({0,{n-1,i}});
    while(q.size())
    {
        pair<long long,pair<int,int> >z=q.top();
        q.pop();
        int x=z.second.first,y=z.second.second;
        for(int j=0; j<3; j++)
        {
            int tx=x+xx[j],ty=y+yy[j],w;
            if(0>tx||tx>=n||0>ty||ty>=m)continue;
            if(j==0)w=v[tx][ty];
            if(j==1)w=h[tx][ty];
            if(j==2)w=h[x][y];

            if(dis[tx][ty][i]>dis[x][y][i]+w)
            {
                dis[tx][ty][i]=dis[x][y][i]+w;
                q.push({dis[tx][ty][i],{tx,ty}});
            }
        }
    }
}

void init(int R, int C, int H[5000][200], int V[5000][200])
{
    n=R,m=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];
    }
    for(int i=0;i<m;i++)on[i]=1;
}

void changeH(int P, int Q, int W)
{
    for(int i=0;i<m;i++)on[i]=1;
    h[P][Q]=W;
}

void changeV(int P, int Q, int W)
{
    for(int i=0;i<m;i++)on[i]=1;
    v[P][Q]=W;
}

int escape(int V1, int V2)
{
    if(on[V2])dij(V2);
    on[V2]=0;
    return dis[0][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]
  int res;
      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 35448 KB Output is correct
2 Correct 238 ms 35576 KB Output is correct
3 Correct 314 ms 37100 KB Output is correct
4 Correct 233 ms 35448 KB Output is correct
5 Correct 238 ms 35452 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 25 ms 1144 KB Output is correct
5 Correct 6 ms 1144 KB Output is correct
6 Correct 28 ms 1144 KB Output is correct
7 Correct 21 ms 1144 KB Output is correct
8 Correct 44 ms 1124 KB Output is correct
9 Correct 39 ms 1144 KB Output is correct
10 Correct 41 ms 1144 KB Output is correct
11 Correct 130 ms 2168 KB Output is correct
12 Correct 62 ms 1272 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20089 ms 17184 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20030 ms 55544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20063 ms 17292 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 20081 ms 17168 KB Time limit exceeded
2 Halted 0 ms 0 KB -