Submission #72529

#	Time	Username	Problem	Language	Result	Execution time	Memory
72529		마릴린 희정 (#118)	Aquatic Labyrinth (FXCUP3_aqua)	C++17	100 / 100	1162 ms	161952 KiB

aqua

#include<bits/stdc++.h>
using namespace std;
int N, sx, sy, ex, ey;
const int MAXN = 4030303;
char arr[1010][1010];

int st;
vector<pair<int, int> > conn[MAXN];
bool visit[MAXN];
int tp;

int dijk()
{
  priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > Q;
  Q.emplace(0, sx*N+sy);
  while(!Q.empty())
  {
    int dist, no; tie(dist, no) = Q.top(); Q.pop();
    //printf("%d\n", no);
    if(no==ex*N+ey) return dist;
    if(visit[no]) continue;
    visit[no] = true;
    for(auto x: conn[no])
    {
      int targ, w;
      tie(targ, w) = x;
      Q.emplace(w+dist, targ);
    }
  }
  return -1;
}

int main()
{
  scanf("%d", &N); tp = N*N+N+1;
  for(int i=1; i<=N; ++i)
    scanf("%s", arr[i]+1);
  for(int i=1; i<=N; ++i)
    for(int j=1; j<=N; ++j)
    {
      if(arr[i][j] == 'M')
      {
        tie(sx, sy) = tie(i, j);
        arr[i][j] = '.';
      }
      if(arr[i][j] == 'H')
      {
        tie(ex, ey) = tie(i, j);
        arr[i][j] = '.';
      }
    }
  for(int i=1; i<=N; ++i)
  {
    int cnt = -1;
    vector<int> inserted;
    vector<int> weight;
    for(int j=0; j<=N+1; ++j)
    {
      if(arr[i][j] == '.')
      {
        if(arr[i][j-1] != '.')
        {
          weight.push_back(cnt);
          inserted.push_back(tp);
        }
        conn[tp].emplace_back(i*N+j, 0);
        conn[i*N+j].emplace_back(tp+1, 0);
      }
      else
      {
        if(j!=0 && arr[i][j-1] == '.')
          cnt = 0, tp += 2;
        ++cnt;
      }
    }
    for(int i=0; i<(int)inserted.size()-1; ++i)
    {
      int ptp = inserted[i], ntp = inserted[i+1], w = weight[i+1]*weight[i+1];
      conn[ptp+1].emplace_back(ntp, w);
      conn[ntp+1].emplace_back(ptp, w);
    }
  }
  for(int j=1; j<=N; ++j)
  {
    int cnt = -1;
    vector<int> inserted, weight;
    for(int i=0; i<=N+1; ++i)
    {
      if(arr[i][j] == '.')
      {
        if(arr[i-1][j] != '.')
        {
          weight.push_back(cnt);
          inserted.push_back(tp);
        }
        conn[tp].emplace_back(i*N+j, 0);
        conn[i*N+j].emplace_back(tp+1, 0);
      }
      else
      {
        if(i!=0 && arr[i-1][j] == '.')
          cnt=0, tp += 2;
        ++cnt;
      }
    }
    for(int i=0; i<(int)inserted.size()-1; ++i)
    {
      int ptp = inserted[i], ntp = inserted[i+1], w = weight[i+1]*weight[i+1];
      conn[ptp+1].emplace_back(ntp, w);
      conn[ntp+1].emplace_back(ptp, w);
    }
  }
  printf("%d\n", dijk());
}

Compilation message (stderr)

aqua.cpp: In function 'int main()':
aqua.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &N); tp = N*N+N+1;
   ~~~~~^~~~~~~~~~
aqua.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", arr[i]+1);
     ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 36 / 36
• Subtask 2: 64 / 64