Submission #72265

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

aqua

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

const int mx = 909, inf = 1e9;

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];
int 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;
    for(int i = 0; i < n; i++){
        d = 1;
        cur = -1;
        for(int j = 0; j < n; j++){
            if(S[i][j] != 'W'){
                if(cur != -1){
                    if(cur != j-1) G[e(i,cur,0)].emplace_back(e(i,j,d),(j-cur-1)*(j-cur-1));
                    else G[e(i,cur,d)].emplace_back(e(i,j,d),0);
                }
                cur = j;
            }
        }
        d = 2; cur = -1;
        for(int j = n; j--; ){
            if(S[i][j] != 'W'){
                if(cur != -1){
                    if(cur != j+1) G[e(i,cur,0)].emplace_back(e(i,j,d),(j-cur-1)*(j-cur-1));
                    else G[e(i,cur,d)].emplace_back(e(i,j,d),0);
                }
                cur = j;
            }
        }
    }
    for(int j = 0; j < n; j++){
        d = 3; cur = -1;
        for(int i = 0; i < n; i++){
            if(S[i][j] != 'W'){
                if(cur != -1){
                    if(cur != i-1) G[e(cur,j,0)].emplace_back(e(i,j,d),(i-cur-1)*(i-cur-1));
                    else G[e(cur,j,d)].emplace_back(e(i,j,d),0);
                }
                cur = i;
            }
        }
        d = 4; cur = -1;
        for(int i = n; i--;){
            if(S[i][j] != 'W'){
                if(cur != -1){
                    if(cur != i+1) G[e(cur,j,0)].emplace_back(e(i,j,d),(i-cur-1)*(i-cur-1));
                    else G[e(cur,j,d)].emplace_back(e(i,j,d),0);
                }
                cur = i;
            }
        }
    }
}

priority_queue<pii,vector<pii>,greater<pii>> 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()){
        pii t = pq.top(); pq.pop();
        if(t.va > dist[t.vb]) continue;
        for(pii &p : G[t.vb]){
            int tmp = dist[t.vb] + p.vb;
            //printf("tmp = %d, dist[%d] = %d\n",tmp,p.va,dist[p.va]);
            //system("pause");
            if(dist[p.va] > tmp){
                dist[p.va] = tmp;
                pq.emplace(dist[p.va], p.va);
            }
        }
    }
    int 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)])
                    {
                        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("%d ",dist[e(i,j,0)]<inf?:-1);
        }
        puts("");
    }
}

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

Compilation message (stderr)

aqua.cpp: In function 'void debug()':
aqua.cpp:142:45: warning: the omitted middle operand in ?: will always be 'true', suggest explicit middle operand [-Wparentheses]
             printf("%d ",dist[e(i,j,0)]<inf?:-1);
                                             ^
aqua.cpp: In function 'void input()':
aqua.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
aqua.cpp:34:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 0; i < n; i++) scanf("%*c%s",S[i]);
                                ~~~~~^~~~~~~~~~~~~~

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