Submission #72297

#	Time	Username	Problem	Language	Result	Execution time	Memory
72297		유애나 (#118)	Aquatic Labyrinth (FXCUP3_aqua)	C++17	100 / 100	700 ms	103420 KiB

aqua

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;
#define X first
#define Y second

const int N = 905, INF = int(1e9);

int n, C, rn[N][N], cn[N][N], rh, ch, rm, cm, cnt, d[2 * N * N], r = INF;
char b[N][N];
vector<pii> e[2 * N * N];
priority_queue<pii, vector<pii>, greater<pii>> pq;

int main(){
    scanf("%d", &n);
    C = N * N;
    for(int i = 1; i <= n; i++) scanf("%s", b[i] + 1);
    for(int i = 1; i <= n; i++){
        int lst = -1, cur = 1;
        for(int j = 1; j <= n; j++){
            if(b[i][j] == 'W') cur++;
            else{
                if(cur){
                    cnt++;
                    e[cnt].push_back({cnt + C, 0});
                    if(lst > 0){
                        e[lst + C].push_back({cnt, cur * cur});
                        e[cnt + C].push_back({lst, cur * cur});
                    }
                    cur = 0;
                    lst = cnt;
                }
                if(b[i][j] == 'H') rh = cnt;
                else if(b[i][j] == 'M') rm = cnt;
                rn[i][j] = cnt;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        int lst = -1, cur = 1;
        for(int j = 1; j <= n; j++){
            if(b[j][i] == 'W') cur++;
            else{
                if(cur){
                    cnt++;
                    e[cnt].push_back({cnt + C, 0});
                    if(lst > 0){
                        e[lst + C].push_back({cnt, cur * cur});
                        e[cnt + C].push_back({lst, cur * cur});
                    }
                    cur = 0;
                    lst = cnt;
                }
                if(b[j][i] == 'H') ch = cnt;
                else if(b[j][i] == 'M') cm = cnt;
                cn[j][i] = cnt;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(rn[i][j] && cn[i][j]){
                e[rn[i][j]].push_back({cn[i][j] + C, 0});
                e[cn[i][j]].push_back({rn[i][j] + C, 0});
            }
        }
    }
//  for(int i = 1; i <= n; i++, puts("")) for(int j = 1; j <= n; j++) printf("%d ", rn[i][j]);
//  puts("");
//  for(int i = 1; i <= n; i++, puts("")) for(int j = 1; j <= n; j++) printf("%d ", cn[i][j]);
//  puts("");
    fill(d + 1, d + C + cnt + 1, INF);
    pq.push({0, rm + C});
    pq.push({0, cm + C});
    d[rm + C] = d[cm + C] = 0;
    while(!pq.empty()){
        pii c = pq.top();
        pq.pop();
        if(d[c.Y] < c.X) continue;
        for(pii i : e[c.Y]){
            if(c.X + i.Y < d[i.X]){
                d[i.X] = c.X + i.Y;
                pq.push({d[i.X], i.X});
            }
        }
    }
    //for(int i = 1; i <= cnt; i++) printf("%d : %d\n", i, d[i]);
    for(pii i : e[rh + C]) if(i.Y) r = min(r, d[i.X + C] + i.Y);
    for(pii i : e[ch + C]) if(i.Y) r = min(r, d[i.X + C] + i.Y);
    printf("%d\n", r == INF ? -1 : r);
}

Compilation message (stderr)

aqua.cpp: In function 'int main()':
aqua.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
aqua.cpp:18:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; i++) scanf("%s", b[i] + 1);
                                 ~~~~~^~~~~~~~~~~~~~~~

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