oj.uz

Submission #674724

# Submission time Handle Problem Language Result Execution time Memory
674724 2022-12-26T01:29:31 Z vjudge1 Wall (CEOI14_wall) C++17
100 / 100
 442 ms 68152 KB 
#include<bits/stdc++.h>
const int N=410,M=N*N*4;
int n,m,a[N][N],b[N][N],c[N][N],pre[M];
bool vis[M],bt[N][N],ct[N][N];
long long dis[M];
std::vector<std::pair<int,int>> G[M];
std::priority_queue<std::pair<long long,int>> q;
inline int idx(int u){return (u-1)/(m+1)+1;}
inline int idy(int u){return (u-1)%(m+1)+1;}
inline int id(int i,int j){return (i-1)*(m+1)+j;}
inline int id(int i,int j,int k){return (i-1)*(m+1)+j+k*(n+1)*(m+1);}
inline void add(int u,int v,int w){G[u].push_back({v,w}),G[v].push_back({u,w});}
void dij(int n){
  memset(vis+1,0,n),memset(dis+1,63,n<<3),dis[1]=0,q.push({0,1});
  while(q.size()){
    auto t=q.top(); q.pop(); int u=t.second; if(vis[u])continue; vis[u]=1;
    for(const auto &e:G[u]){int v=e.first,w=e.second;if(dis[v]>dis[u]+w)dis[v]=dis[u]+w,pre[v]=u,q.push({-dis[v],v});}
  }
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
  for(int i=1;i<=n;i++)for(int j=0;j<=m;j++)scanf("%d",&b[i][j]);
  for(int i=0;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&c[i][j]);
  for(int i=1;i<=n;i++)for(int j=0;j<=m;j++)add(id(i,j+1),id(i+1,j+1),b[i][j]);
  for(int i=0;i<=n;i++)for(int j=1;j<=m;j++)add(id(i+1,j),id(i+1,j+1),c[i][j]);
  dij((n+1)*(m+1));
  for(int u=1;u<=(n+1)*(m+1);u++)G[u].clear();
  for(int i=1;i<=n+1;i++)for(int j=1;j<=m+1;j++)if(a[i][j]){
    bt[i][j]=bt[i][j-1]=ct[i][j]=ct[i-1][j]=1;
    for(int u=id(i,j);u!=1;u=pre[u])u>pre[u]?
      (u-pre[u]==1?ct[idx(u)-1][idy(u)-1]:bt[idx(u)-1][idy(u)-1])=1:
      (pre[u]-u==1?ct[idx(pre[u])-1][idy(pre[u])-1]:bt[idx(pre[u])-1][idy(pre[u])-1])=1;
  }
  for(int i=1;i<=n;i++)for(int j=0;j<=m;j++)add(id(i,j+1,3),id(i+1,j+1,0),b[i][j]),add(id(i,j+1,2),id(i+1,j+1,1),b[i][j]);
  for(int i=0;i<=n;i++)for(int j=1;j<=m;j++)add(id(i+1,j,1),id(i+1,j+1,0),c[i][j]),add(id(i+1,j,2),id(i+1,j+1,3),c[i][j]);
  add(id(1,1,0),id(1,1,1),0);
  for(int i=1;i<=n+1;i++)for(int j=i==1?2:1;j<=m+1;j++){
    if(!bt[i-1][j-1])add(id(i,j,0),id(i,j,1),0);//printf("%d %d : %d %d\n",i,j,0,1);
    if(!ct[i-1][j])add(id(i,j,1),id(i,j,2),0);//printf("%d %d : %d %d\n",i,j,1,2);
    if(!bt[i][j-1])add(id(i,j,2),id(i,j,3),0);//printf("%d %d : %d %d\n",i,j,2,3);
    if(!ct[i-1][j-1])add(id(i,j,3),id(i,j,0),0);//printf("%d %d : %d %d\n",i,j,3,0);
  }
  dij((n+1)*(m+1)*4),printf("%lld\n",dis[id(1,1,3)]);
}

Compilation message

wall.cpp: In function 'int main()':
wall.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   scanf("%d%d",&n,&m);
      |   ~~~~~^~~~~~~~~~~~~~
wall.cpp:22:50: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |   for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
      |                                             ~~~~~^~~~~~~~~~~~~~~
wall.cpp:23:50: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   for(int i=1;i<=n;i++)for(int j=0;j<=m;j++)scanf("%d",&b[i][j]);
      |                                             ~~~~~^~~~~~~~~~~~~~~
wall.cpp:24:50: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   for(int i=0;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&c[i][j]);
      |                                             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16212 KB Output is correct
2 Correct 9 ms 16212 KB Output is correct
3 Correct 9 ms 16212 KB Output is correct
4 Correct 10 ms 16212 KB Output is correct
5 Correct 10 ms 16152 KB Output is correct
6 Correct 11 ms 16496 KB Output is correct
7 Correct 10 ms 16468 KB Output is correct
8 Correct 10 ms 16468 KB Output is correct
9 Correct 10 ms 16364 KB Output is correct
10 Correct 10 ms 16468 KB Output is correct
11 Correct 11 ms 16620 KB Output is correct
12 Correct 11 ms 16724 KB Output is correct
13 Correct 12 ms 16756 KB Output is correct
14 Correct 11 ms 16724 KB Output is correct
15 Correct 11 ms 16696 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16644 KB Output is correct
2 Correct 12 ms 16724 KB Output is correct
3 Correct 12 ms 16716 KB Output is correct
4 Correct 12 ms 16788 KB Output is correct
5 Correct 13 ms 16664 KB Output is correct
6 Correct 12 ms 16772 KB Output is correct
7 Correct 13 ms 16756 KB Output is correct
8 Correct 11 ms 16764 KB Output is correct
9 Correct 11 ms 16652 KB Output is correct
10 Correct 12 ms 16880 KB Output is correct
11 Correct 12 ms 16724 KB Output is correct
12 Correct 14 ms 16724 KB Output is correct
13 Correct 11 ms 16724 KB Output is correct
14 Correct 11 ms 16724 KB Output is correct
15 Correct 13 ms 16816 KB Output is correct
16 Correct 13 ms 16748 KB Output is correct
17 Correct 14 ms 16884 KB Output is correct
18 Correct 12 ms 16724 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 27984 KB Output is correct
2 Correct 75 ms 26156 KB Output is correct
3 Correct 69 ms 27068 KB Output is correct
4 Correct 79 ms 27244 KB Output is correct
5 Correct 188 ms 41736 KB Output is correct
6 Correct 83 ms 27968 KB Output is correct
7 Correct 219 ms 44228 KB Output is correct
8 Correct 208 ms 43468 KB Output is correct
9 Correct 171 ms 43468 KB Output is correct
10 Correct 231 ms 44756 KB Output is correct
11 Correct 258 ms 46128 KB Output is correct
12 Correct 67 ms 27664 KB Output is correct
13 Correct 194 ms 42336 KB Output is correct
14 Correct 327 ms 59040 KB Output is correct
15 Correct 353 ms 62740 KB Output is correct
16 Correct 335 ms 63684 KB Output is correct
17 Correct 442 ms 65840 KB Output is correct
18 Correct 430 ms 68152 KB Output is correct
19 Correct 415 ms 63752 KB Output is correct
20 Correct 357 ms 62924 KB Output is correct