Submission #72279

#	Time	Username	Problem	Language	Result	Execution time	Memory
72279		BOJ 8481 (#118)	Aquatic Labyrinth (FXCUP3_aqua)	C++17	0 / 100	3 ms	488 KiB

aqua

#include <bits/stdc++.h>
#define dbgv(v) {for(auto x:v)cout<<x<<' ';cout<<'\n';}
#define entire(v) v.begin(),v.end()
typedef long long ll;
using namespace std;
void OJize(){
    cin.tie(NULL); ios_base::sync_with_stdio(false);
    #ifdef jh
    freopen("input.txt", "r", stdin);
    #endif
}

// if you want to use ll, remember to change 0x3f3f3f3f!!
const int INF = 0x3f3f3f3f3f3f3f3f;
template <typename T>
struct WGraph{
    int n; vector<vector<pair<int,T>>> adj;
    WGraph(int n): n{n}, adj{vector<vector<pair<int,T>>>(n+1)} {}
    void connect(int a, int b, T c){
        //cout<<"Connected "<<a<<' '<<b<<' '<<c<<'\n';
        adj[a].push_back({b,c});}
    void input(int m){
        int a,b,c;
        for(int i=0;i<m;i++){cin>>a>>b>>c; connect(a,b,c);}
    }

    vector<T> dijkstra(int v){
        set<pair<T,int>> S; S.insert(make_pair(0,v));
        vector<T> dist(n+1, INF); dist[v] = 0;
        while(!S.empty()){
            int v = (*S.begin()).second, u; T c; S.erase(S.begin());
            for(auto& uc:adj[v]){
                tie(u,c) = uc;
                if(dist[u] <= dist[v]+c) continue;
                if(dist[u] != INF) S.erase(S.find({dist[u],u}));
                dist[u] = dist[v]+c; S.insert({dist[u],u});
            }
        }
        return dist;
    }
};

string grid[911];
int main(){OJize();
    // Get the grid
    int n; cin>>n;
    int si, sj, ei, ej;
    for(int i=0; i<n; i++){
        cin>>grid[i];
        for(int j=0; j<n; j++){
            if(grid[i][j] == 'M') si = i, sj = j;
            if(grid[i][j] == 'H') ei = i, ej = j;
        }
    }
    WGraph<ll> G(n*n);
    
    // Right
    for(int i=0; i<n; i++){
        int water = 0;
        int j1 = 0;
        while(j1<n && grid[i][j1] == 'W') j1++;
        int j2 = j1;
        for(; j1<n; j1++){
            if(j1 != j2 && grid[i][j1] != 'W'){G.connect(n*i+j1, n*i+j2, water*water); continue;}
            if(grid[i][j1] == 'W') continue;
            water = 0;
            while(j2<n && grid[i][j2] != 'W') j2++;
            while(j2<n && grid[i][j2] == 'W') j2++, water++;
            if(j2 == n) break;
            G.connect(n*i+j1, n*i+j2, water*water);
        }
    }
    
    // Left
    for(int i=0; i<n; i++){
        int water = 0;
        int j1 = n-1;
        while(j1>=0 && grid[i][j1] == 'W') j1--;
        int j2 = j1;
        for(; j1>=0; j1--){
            if(j1 != j2 && grid[i][j1] != 'W'){G.connect(n*i+j1, n*i+j2, water*water); continue;}
            if(grid[i][j1] == 'W') continue;
            water = 0;
            while(j2>=0 && grid[i][j2] != 'W') j2--;
            while(j2>=0 && grid[i][j2] == 'W') j2--, water++;
            if(j2 == -1) break;
            G.connect(n*i+j1, n*i+j2, water*water);
        }
    }

    // Down
    for(int j=0; j<n; j++){
        int water = 0;
        int i1 = 0;
        while(i1<n && grid[i1][j] == 'W') i1++;
        int i2 = i1;
        for(; i1<n; i1++){
            if(i1 != i2 && grid[i1][j] != 'W'){G.connect(n*i1+j, n*i2+j, water*water); continue;}
            if(grid[i1][j] == 'W') continue;
            water = 0;
            while(i2<n && grid[i2][j] != 'W') i2++;
            while(i2<n && grid[i2][j] == 'W') i2++, water++;
            if(i2 == n) break;
            G.connect(n*i1+j, n*i2+j, water*water);
        }
    }
    
    // Up
    for(int j=0; j<n; j++){
        int water = 0;
        int i1 = n-1;
        while(i1>=0 && grid[i1][j] == 'W') i1--;
        int i2 = i1;
        for(; i1>=0; i1--){
            if(i1 != i2 && grid[i1][j] != 'W'){G.connect(n*i1+j, n*i2+j, water*water); continue;}
            if(grid[i1][j] == 'W') continue;
            water = 0;
            while(i2>=0 && grid[i2][j] != 'W') i2--;
            while(i2>=0 && grid[i2][j] == 'W') i2--, water++;
            if(i2 == -1) break;
            G.connect(n*i1+j, n*i2+j, water*water);
        }
    }
    
    ll ans = G.dijkstra(n*si+sj)[n*ei+ej];
    cout << (ans != INF? ans : -1);
}

Compilation message (stderr)

aqua.cpp:14:17: warning: overflow in implicit constant conversion [-Woverflow]
 const int INF = 0x3f3f3f3f3f3f3f3f;
                 ^~~~~~~~~~~~~~~~~~
aqua.cpp: In function 'int main()':
aqua.cpp:125:38: warning: 'ej' may be used uninitialized in this function [-Wmaybe-uninitialized]
     ll ans = G.dijkstra(n*si+sj)[n*ei+ej];
                                  ~~~~^~~
aqua.cpp:125:35: warning: 'ei' may be used uninitialized in this function [-Wmaybe-uninitialized]
     ll ans = G.dijkstra(n*si+sj)[n*ei+ej];
                                  ~^~~
aqua.cpp:125:24: warning: 'sj' may be used uninitialized in this function [-Wmaybe-uninitialized]
     ll ans = G.dijkstra(n*si+sj)[n*ei+ej];
              ~~~~~~~~~~^~~~~~~~~
aqua.cpp:125:26: warning: 'si' may be used uninitialized in this function [-Wmaybe-uninitialized]
     ll ans = G.dijkstra(n*si+sj)[n*ei+ej];
                         ~^~~

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