oj.uz

Submission #14535

# Submission time Handle Problem Language Result Execution time Memory
14535 2015-05-19T13:51:39 Z gs14004 물병 (JOI14_bottle) C++14
0 / 100
 5000 ms 135152 KB 
#include <stdio.h>
#include <queue>
#include <stdlib.h> 
int h,w,p,q;
struct Coor2{
   int x,y;
   int dis;
};
struct Coor{
   int x,y;
}b[2010];
char a[2010][2010];
int DT[5010][5010];
int dis[2010][2010];
int visit[2010][2010];
int dx[4] = {0,1,0,-1};
int dy[4] = {-1,0,1,0};
std::queue<Coor2> Q;
int max(int a,int b)
{
   return a>b?a:b;
}
void g(){
   for(int k=1;k<=p;k++){
      for(int i=1;i<=p;i++){
         for(int j=1;j<=p;j++){
            if(max(dis[i][k],dis[k][j]) < dis[i][j]){
               dis[i][j] = max(dis[i][k],dis[k][j]);
            }
         }
      }
   }
}
int getDis(int st,int ed){
   while(!Q.empty()){
      Q.pop();
   }
   int ex = b[ed].x;
   int ey = b[ed].y;
   Coor2 init;
   init.x = b[st].x;
   init.y = b[st].y;
   init.dis = 0;
   Q.push(init);
   while(!Q.empty()){
      Coor2 cur = Q.front();
      Q.pop();
      if(cur.x==ex&&cur.y==ey){
         return cur.dis;
      }
      for(int i=0;i<4;i++){
         if(cur.x+dx[i]>=0 && cur.x+dx[i]<h && cur.y+dy[i]>=0 && cur.y+dy[i]<w && a[cur.x+dx[i]][cur.y+dy[i]] == '.'&&visit[cur.x+dx[i]][cur.y+dy[i]] != st*(2*p)+ed){
            Coor2 next;
            next.x = cur.x+dx[i];
            next.y = cur.y+dy[i];
            visit[next.x][next.y] = st*(2*p)+ed;
            if(next.x==ex&&next.y==ey){
               return cur.dis;
            }
            next.dis = cur.dis+1;
            Q.push(next);
         }
      }
   }
   return 987654321;
}
void preinit(){
   for(int i=1;i<=p;i++){
      for(int j=1;j<=p;j++){
         dis[i][j] = getDis(i,j);
      }
   }
}
int dijkstra(int st,int ed){
   
}
int main()
{
   scanf("%d %d %d %d",&h,&w,&p,&q);
   if(p>=5010){
      printf("Cutting"); 
      return 0;
   }
   for(int i=0;i<h;i++){
      scanf("%s",a[i]);
   }
   for(int i=1;i<=p;i++){
      int x,y;
      scanf("%d %d",&x,&y);
      b[i].x = x-1;
      b[i].y = y-1;
   }
   preinit();
   /*if(q==1){
      int s,t;
      scanf("%d %d",&s,&t);
      printf("%d",dijkstra(s,t));
   }*/
   //else{
      g();
      for(int i=1;i<=q;i++){
         int s,t;
         scanf("%d %d",&s,&t);
         if(dis[s][t]==987654321) printf("-1");
         else printf("%d",dis[s][t]);
      }
   //}
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5000 ms 135148 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5000 ms 135148 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5000 ms 135148 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 135152 KB Output isn't correct
2 Halted 0 ms 0 KB -