oj.uz

Submission #69321

# Submission time Handle Problem Language Result Execution time Memory
69321 2018-08-20T12:26:08 Z MKopchev Wombats (IOI13_wombats) C++14
37 / 100
 20000 ms 21012 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<=100)
    {
        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 121 ms 12408 KB Output is correct
2 Correct 122 ms 12408 KB Output is correct
3 Correct 229 ms 13952 KB Output is correct
4 Correct 126 ms 13952 KB Output is correct
5 Correct 123 ms 13952 KB Output is correct
6 Correct 3 ms 13952 KB Output is correct
7 Correct 2 ms 13952 KB Output is correct
8 Correct 3 ms 13952 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13952 KB Output is correct
2 Correct 3 ms 13952 KB Output is correct
3 Correct 3 ms 13952 KB Output is correct
4 Correct 16 ms 13952 KB Output is correct
5 Correct 4 ms 13952 KB Output is correct
6 Correct 18 ms 13952 KB Output is correct
7 Correct 14 ms 13952 KB Output is correct
8 Correct 16 ms 13952 KB Output is correct
9 Correct 17 ms 13952 KB Output is correct
10 Correct 20 ms 13952 KB Output is correct
11 Correct 111 ms 13952 KB Output is correct
12 Correct 21 ms 13952 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 13952 KB Output is correct
2 Correct 398 ms 13952 KB Output is correct
3 Correct 466 ms 13952 KB Output is correct
4 Correct 399 ms 13952 KB Output is correct
5 Correct 388 ms 13952 KB Output is correct
6 Correct 3 ms 13952 KB Output is correct
7 Correct 2 ms 13952 KB Output is correct
8 Correct 3 ms 13952 KB Output is correct
9 Correct 502 ms 13952 KB Output is correct
10 Correct 3 ms 13952 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1564 ms 20648 KB Output is correct
2 Correct 3146 ms 20648 KB Output is correct
3 Correct 1496 ms 20684 KB Output is correct
4 Execution timed out 20095 ms 20960 KB Time limit exceeded

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 20960 KB Output is correct
2 Correct 376 ms 20960 KB Output is correct
3 Correct 427 ms 20960 KB Output is correct
4 Correct 378 ms 20960 KB Output is correct
5 Correct 357 ms 20960 KB Output is correct
6 Correct 1544 ms 20960 KB Output is correct
7 Correct 3158 ms 20960 KB Output is correct
8 Correct 1575 ms 20960 KB Output is correct
9 Execution timed out 20062 ms 21012 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 21012 KB Output is correct
2 Correct 423 ms 21012 KB Output is correct
3 Correct 408 ms 21012 KB Output is correct
4 Correct 368 ms 21012 KB Output is correct
5 Correct 380 ms 21012 KB Output is correct
6 Correct 1646 ms 21012 KB Output is correct
7 Correct 2524 ms 21012 KB Output is correct
8 Correct 1583 ms 21012 KB Output is correct
9 Execution timed out 20018 ms 21012 KB Time limit exceeded
10 Halted 0 ms 0 KB -