Submission #72370

#	Time	Username	Problem	Language	Result	Execution time	Memory
72370		IDxTree (#118)	Aquatic Labyrinth (FXCUP3_aqua)	C++17	0 / 100	86 ms	97508 KiB

aqua

#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
typedef pair<int,int> pii;

const int mx = 909;
const ll inf = 1e15;

int n, sq;

int e(int i, int j, int v)
{
    return v * sq + i * n + j;
}
int e(int x, int v)
{
    return v * sq + x;
}

void d(int v)
{
    //printf("%d %d %d",v%n,(v%sq)/n,v/sq);
}

bool ok(int i, int j)
{
    return 0 <= i && i < n && 0 <= j && j < n;
}

char S[mx][mx];
vector<pii> G[5*mx*mx];
ll dist[5*mx*mx];
int M, H;

void input()
{
    scanf("%d",&n);
    sq = n * n;
    for(int i = 0; i < n; i++)
        scanf("%*c%s",S[i]);
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(S[i][j] == 'M')
                M = e(i,j,0);
            if(S[i][j] == 'H')
                H = e(i,j,0);
            if(S[i][j] == 'W')
                continue;
            for(int t = 1; t <= 4; t++)
            {
                G[e(i,j,t)].emplace_back(e(i,j,0),0);
            }
        }
    }
    int d = 0, cur, cur2;
    for(int i = 0; i < n; i++)
    {
        d = 1;
        cur = -1;
        cur2 = -1;
        for(int j = 0; j < n; j++)
        {
            if(S[i][j] != 'W')
            {
                if(cur != -1)
                {
                    if(cur2 != j-1)
                    {
                        //printf("i = %d d = %d, cur = %d, cur2 = %d\n",i,d,cur,cur2);
                        for(int f = cur; f <= cur2; f++)
                            G[e(i,f,0)].emplace_back(e(i,j,d),(j-cur2-1)*(j-cur2-1));
                        cur = cur2 = j;
                    }
                    else
                    {
                        G[e(i,cur2,d)].emplace_back(e(i,j,d),0);
                        cur2 = j;
                    }
                }
                else cur = cur2 = j;
            }
        }
        d = 2;
        cur = -1; cur2 = -1;
        for(int j = n - 1; j >= 0; j--)
        {
            if(S[i][j] != 'W')
            {
                if(cur != -1)
                {
                    if(cur2 != j+1)
                    {
                        //printf("i = %d d = %d, cur = %d, cur2 = %d\n",i,d,cur,cur2);
                        for(int f = cur2; f <= cur; f++)
                            G[e(i,f,0)].emplace_back(e(i,j,d),(cur2-i-1)*(cur2-i-1));
                        cur = cur2 = j;
                    }
                    else
                    {
                        G[e(i,cur2,d)].emplace_back(e(i,j,d),0);
                        cur2 = j;
                    }
                }
                else cur = cur2 = j;
            }
        }
    }
    for(int j = 0; j < n; j++)
    {
        d = 3;
        cur = -1;
        cur2 = -1;
        for(int i = 0; i < n; i++)
        {
            if(S[i][j] != 'W')
            {
                if(cur != -1)
                {
                    if(cur2 != i-1)
                    {
                        //printf("j = %d d = %d, cur = %d, cur2 = %d\n",j,d,cur,cur2);
                        for(int f = cur; f <= cur2; f++)
                            G[e(f,j,0)].emplace_back(e(i,j,d),(i-cur2-1)*(i-cur2-1));
                        cur = cur2 = i;
                    }
                    else
                    {
                        G[e(cur2,j,d)].emplace_back(e(i,j,d),0);
                        cur2 = i;
                    }
                }
                else cur = cur2 = i;
            }
        }
        d = 4;
        cur = -1;
        cur2 = -1;
        for(int i = n-1; i >= 0; i--)
        {
            if(S[i][j] != 'W')
            {
                if(cur != -1)
                {
                    if(cur2 != i+1)
                    {
                        //printf("j = %d d = %d, cur = %d, cur2 = %d\n",j,d,cur,cur2);
                        for(int f = cur2; f <= cur; f++)
                            G[e(f,j,0)].emplace_back(e(i,j,d),(cur2-i-1)*(cur2-i-1));
                        cur = cur2 = i;
                    }
                    else
                    {
                        G[e(cur2,j,d)].emplace_back(e(i,j,d),0);
                        cur2 = i;
                    }
                }
                else cur = cur2 = i;
            }
        }
    }
}

priority_queue<pli,vector<pli>,greater<pli>> pq;

void dijk()
{
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            for(int d = 0; d <= 4; d++)
                dist[e(i,j,d)] = inf;
    dist[M] = 0;
    pq.emplace(0,M);
    while(!pq.empty())
    {
        pli t = pq.top();
        pq.pop();
        if(t.va > dist[t.vb])
            continue;
        for(pii &p : G[t.vb])
        {
            ll tmp = dist[t.vb] + p.vb;
            ////printf("tmp = %d, now = %d, dist[%d] = %d\n",tmp,t.vb,p.va,dist[p.va]);
            //system("pause");
            if(dist[p.va] > tmp)
            {
                dist[p.va] = tmp;
                pq.emplace(dist[p.va], p.va);
            }
        }
    }
    ll ans = inf;
    for(int t = 0; t <= 4; t++)
    {
        ans = min(ans, dist[e(H,t)]);
    }
    cout << (ans == inf ? -1 : ans) << '\n';
}

void debug()
{
    for(int k = 0; k < 5; k++)
    {
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                //for(int k = 0; k < 5; k++)
                {
                    for(pii &p : G[e(i,j,k)])
                    {
                        if(p.va % sq == 2)
                            printf("%d -> %d, cost = %d\n",e(i,j,k),p.va,p.vb);
                    }
                }
            }
        }
    }
    printf("M = %d, H = %d\n",M,H);
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            printf("%2lld ",dist[e(i,j,0)]<inf?dist[e(i,j,0)]:-1LL);
        }
        puts("");
    }
}

int main()
{
    //freopen("sample.txt","rt",stdin);
    input();
    dijk();
    //debug();
}

Compilation message (stderr)

aqua.cpp: In function 'void input()':
aqua.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
aqua.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%*c%s",S[i]);
         ~~~~~^~~~~~~~~~~~~~

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