제출 #69320

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
69320		MKopchev	웜뱃 (IOI13_wombats)	C++14	55 / 100	20021 ms	46840 KiB

wombats

#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;
}
*/

컴파일 시 표준 에러 (stderr) 메시지

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 / 9
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24