제출 #756866

#제출 시각아이디문제언어결과실행 시간메모리
756866DJeniUp웜뱃 (IOI13_wombats)C++17
55 / 100
20026 ms81880 KiB
#include "wombats.h" #include "bits/stdc++.h" #pragma GCC optimize("Ofast") #pragma GCC optimize("O3") using namespace std; typedef int ll; typedef pair<ll,ll>pairll; #define pb push_back #define fr first #define sc second #define A 16 #define INF 1000000007 ll h[5007][207],v[5007][207],n,m,f[207],res[207][207],g[5007][207],l[2][207]; ll d[5007/A+1][207][207]; priority_queue<pairll, vector<pairll>, greater<pairll> >q; void S(ll x){ //cout<<x<<endl; ll y=x; y*=A; for(int k=0;k<m;k++){ for(int i=y;i<=y+A;i++){ for(int j=0;j<m;j++){ g[i][j]=INF; } } g[y][k]=0; q.push({0,y*m+k}); while(q.size()>0){ ll m1=q.top().fr; ll x1=q.top().sc/m; ll y1=q.top().sc%m; q.pop(); if(x1<min(n-1,y+A)){ if(g[x1+1][y1]>m1+v[x1][y1]){ g[x1+1][y1]=m1+v[x1][y1]; q.push({m1+v[x1][y1],m*(x1+1)+y1}); } } if(y1>0){ if(g[x1][y1-1]>m1+h[x1][y1-1]){ g[x1][y1-1]=m1+h[x1][y1-1]; q.push({m1+h[x1][y1-1],x1*m+y1-1}); } } if(y1<m-1){ if(g[x1][y1+1]>m1+h[x1][y1]){ g[x1][y1+1]=m1+h[x1][y1]; q.push({m1+h[x1][y1],x1*m+y1+1}); } } } for(int j=0;j<m;j++){ d[x][k][j]=g[min(n-1,y+A)][j]; } } return ; } void R(ll x){ f[x]=1; for(int i=0;i<m;i++){ l[0][i]=INF; } l[0][x]=0; for(int i=0;i<=(n-1)/A;i++){ for(int j=0;j<m;j++){ l[1][j]=INF; for(int k=0;k<m;k++){ l[1][j]=min(l[1][j],l[0][k]+d[i][k][j]); } } swap(l[0],l[1]); } for(int i=0;i<m;i++){ res[x][i]=l[0][i]; } return ; } void init(int R, int C, int H[5000][200], int V[5000][200]) { n=R; m=C; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ h[i][j]=H[i][j]; v[i][j]=V[i][j]; } } for(int i=0;i<=(n-1)/A;i++){ S(i); } return ; } void changeH(int x, int y, int val) { h[x][y]=val; for(int i=0;i<m;i++){ f[i]=0; } if(x%A==0){ if(x!=0)S(x/A-1); } S(x/A); return ; } void changeV(int x, int y, int val) { for(int i=0;i<m;i++){ f[i]=0; } v[x][y]=val; S(x/A); return ; } int escape(int y1, int y2) { if(f[y1]==0){ R(y1); } return res[y1][y2]; }

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

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...