oj.uz

Submission #69320

# Submission time Handle Problem Language Result Execution time Memory
69320 2018-08-20T12:24:02 Z MKopchev Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 46840 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;
}
int in=0;
void changeH(int P,int Q,int W)
{
    in=0;
    h[P][Q]=W;
    run=1;
}
void changeV(int P,int Q,int W)
{
    in=0;
    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 slow(int x1,int y1,int x2,int y2)
{
    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==x2&&y==y2)return 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}});
    }
    assert(0==1);
}






int escape(int V1,int V2)
{
    if(in<=10)
    {
        in++;
        return slow(0,V1,r-1,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:60: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 119 ms 12280 KB Output is correct
3 Correct 253 ms 13980 KB Output is correct
4 Correct 120 ms 13980 KB Output is correct
5 Correct 126 ms 13980 KB Output is correct
6 Correct 3 ms 13980 KB Output is correct
7 Correct 3 ms 13980 KB Output is correct
8 Correct 2 ms 13980 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 13980 KB Output is correct
2 Correct 380 ms 13980 KB Output is correct
3 Correct 383 ms 13980 KB Output is correct
4 Correct 400 ms 13980 KB Output is correct
5 Correct 413 ms 13980 KB Output is correct
6 Correct 3 ms 13980 KB Output is correct
7 Correct 2 ms 13980 KB Output is correct
8 Correct 2 ms 13980 KB Output is correct
9 Correct 378 ms 13980 KB Output is correct
10 Correct 4 ms 13980 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1398 ms 20676 KB Output is correct
2 Correct 2467 ms 20676 KB Output is correct
3 Correct 1787 ms 20736 KB Output is correct
4 Correct 10276 ms 21460 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 448 ms 21460 KB Output is correct
2 Correct 356 ms 21460 KB Output is correct
3 Correct 360 ms 21460 KB Output is correct
4 Correct 388 ms 21460 KB Output is correct
5 Correct 358 ms 21460 KB Output is correct
6 Correct 1521 ms 21460 KB Output is correct
7 Correct 2482 ms 21460 KB Output is correct
8 Correct 1370 ms 21460 KB Output is correct
9 Correct 9862 ms 21680 KB Output is correct
10 Correct 148 ms 21680 KB Output is correct
11 Correct 135 ms 21680 KB Output is correct
12 Correct 204 ms 21680 KB Output is correct
13 Correct 136 ms 21680 KB Output is correct
14 Correct 119 ms 21680 KB Output is correct
15 Correct 2 ms 21680 KB Output is correct
16 Correct 3 ms 21680 KB Output is correct
17 Correct 3 ms 21680 KB Output is correct
18 Correct 7 ms 21680 KB Output is correct
19 Correct 5 ms 21680 KB Output is correct
20 Correct 6 ms 21680 KB Output is correct
21 Correct 6 ms 21680 KB Output is correct
22 Correct 11 ms 21680 KB Output is correct
23 Correct 7 ms 21680 KB Output is correct
24 Correct 9 ms 21680 KB Output is correct
25 Correct 98 ms 21680 KB Output is correct
26 Correct 8 ms 21680 KB Output is correct
27 Correct 408 ms 21680 KB Output is correct
28 Execution timed out 20010 ms 27648 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 27648 KB Output is correct
2 Correct 406 ms 27648 KB Output is correct
3 Correct 363 ms 27648 KB Output is correct
4 Correct 365 ms 27648 KB Output is correct
5 Correct 364 ms 27648 KB Output is correct
6 Correct 1478 ms 27648 KB Output is correct
7 Correct 2408 ms 27648 KB Output is correct
8 Correct 1391 ms 27648 KB Output is correct
9 Correct 11551 ms 28580 KB Output is correct
10 Correct 133 ms 28580 KB Output is correct
11 Correct 134 ms 28580 KB Output is correct
12 Correct 209 ms 28580 KB Output is correct
13 Correct 133 ms 28580 KB Output is correct
14 Correct 118 ms 28580 KB Output is correct
15 Correct 2682 ms 38660 KB Output is correct
16 Execution timed out 20021 ms 46840 KB Time limit exceeded
17 Halted 0 ms 0 KB -