oj.uz

Submission #69319

# Submission time Handle Problem Language Result Execution time Memory
69319 2018-08-20T12:19:49 Z MKopchev Wombats (IOI13_wombats) C++14
39 / 100
 20000 ms 22256 KB 
#include<bits/stdc++.h>
#include"wombats.h"
using namespace std;
const int rmax=5e3+5,cmax=2e2+5;
int r,c,h[rmax][cmax],v[rmax][cmax];
bool run=0;
int mem[cmax][cmax];
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];
    run=1;
}
void changeH(int P,int Q,int W)
{
    h[P][Q]=W;
    run=1;
}
void changeV(int P,int Q,int W)
{
    v[P][Q]=W;
    run=1;
}
int dist[rmax][cmax];
priority_queue< pair<int,pair<int,int> > > pq,idle;
int dij(int x1,int y1)
{
    for(int i=0;i<r;i++)
        for(int j=0;j<c;j++)
            dist[i][j]=-1;
    pq=idle;
        pq.push({0,{x1,y1}});
    pair<int,pair<int,int> > p;
    int d,x,y;
    while(pq.size())
    {
        p=pq.top();
        pq.pop();
        d=-p.first;
        x=p.second.first;
        y=p.second.second;
        //cout<<x<<" "<<y<<" -> "<<d<<endl;
        if(dist[x][y]!=-1)continue;
        dist[x][y]=d;
        if(x!=r-1)pq.push({-(d+v[x][y]),{x+1,y}});
        if(y)pq.push({-(d+h[x][y-1]),{x,y-1}});
        if(y!=c-1)pq.push({-(d+h[x][y]),{x,y+1}});
    }
    for(int j=0;j<c;j++)
        mem[y1][j]=dist[r-1][j];
}
int escape(int V1,int V2)
{
    if(run)
    {
        for(int j=0;j<c;j++)
            dij(0,j);
        run=0;
    }
    return mem[V1][V2];
}
/*
int H[5000][200]={
{0,2,5},
{7,1,1},
{0,4,0}
};
int V[5000][200]={
{0,0,0,2},
{0,3,4,7},
};
int main()
{
init(3,4,H,V);
cout<<escape(2,1)<<endl;//2
cout<<escape(3,3)<<endl;//7
changeV(0,0,5);
changeH(1,1,6);
cout<<escape(2,1)<<endl;//5
return 0;
}
*/

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;
      ^~~
wombats.cpp: In function 'int dij(int, int)':
wombats.cpp:57:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 12280 KB Output is correct
2 Correct 115 ms 12380 KB Output is correct
3 Correct 230 ms 14316 KB Output is correct
4 Correct 120 ms 14316 KB Output is correct
5 Correct 125 ms 14316 KB Output is correct
6 Correct 3 ms 14316 KB Output is correct
7 Correct 2 ms 14316 KB Output is correct
8 Correct 3 ms 14316 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14316 KB Output is correct
2 Correct 3 ms 14316 KB Output is correct
3 Correct 2 ms 14316 KB Output is correct
4 Correct 8 ms 14316 KB Output is correct
5 Correct 5 ms 14316 KB Output is correct
6 Correct 6 ms 14316 KB Output is correct
7 Correct 6 ms 14316 KB Output is correct
8 Correct 5 ms 14316 KB Output is correct
9 Correct 5 ms 14316 KB Output is correct
10 Correct 5 ms 14316 KB Output is correct
11 Correct 99 ms 14316 KB Output is correct
12 Correct 6 ms 14316 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2446 ms 14316 KB Output is correct
2 Execution timed out 20027 ms 14316 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1627 ms 21140 KB Output is correct
2 Correct 2776 ms 21232 KB Output is correct
3 Correct 1505 ms 21232 KB Output is correct
4 Correct 1532 ms 22256 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2258 ms 22256 KB Output is correct
2 Execution timed out 20097 ms 22256 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2375 ms 22256 KB Output is correct
2 Execution timed out 20045 ms 22256 KB Time limit exceeded
3 Halted 0 ms 0 KB -