Submission #72376

# Submission time Handle Problem Language Result Execution time Memory
72376 2018-08-26T07:33:49 Z BOJ 8481(#2179, veydpz, jh05013, 16silver) Aquatic Labyrinth (FXCUP3_aqua) C++17
36 / 100
3000 ms 257836 KB
#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
}

string grid[911];
int n=0;

int gid(int i, int j, int dir){
    // S R L D U
    return 5*(n*i+j)+dir;
}

char destruct(int v){
    int dir = v%5; v/= 5;
    int i = v/n, j = v%n;
    cout<<'('<<i<<' '<<j<<' '<<dir<<')';
    return ' ';
}

// if you want to use ll, remember to change 0x3f3f3f3f!!
const ll 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 ";
        //cout<<destruct(a);
        //cout<<destruct(b);
        //cout<<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);}
    }

    T dijkstra(int v, int u){
        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[u];
    }
};

int main(){OJize();
    // Get the grid
    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(5*n*n);
    
    // Landing
    for(int i=0; i<n; i++) for(int j=0; j<n; j++) if(grid[i][j] != 'W'){
        for(int d=1; d<=4; d++) G.connect(gid(i,j,d), gid(i,j,0), 0);
    }
    
    // Right
    int dir = 1;
    for(int i=0; i<n; i++){
        int memo1 = -1;
        int j = 0;
        while(j<n && grid[i][j] == 'W') j++;
        for(; j<n; j++){
            char prev = j==0? 'W':grid[i][j-1];
            char curr = grid[i][j];
            if(prev != 'W' && curr != 'W' && memo1 != -1) G.connect(gid(i,j,0), memo1, 0); // Same wall
            else if(prev != 'W' && curr == 'W'){
                // A new wall
                memo1 = -1;
                int j2 = j, water = 0;
                while(j2<n && grid[i][j2] == 'W') j2++, water++;
                for(; j2<n && grid[i][j2] != 'W'; j2++) G.connect(gid(i,j,dir), gid(i,j2,dir), water*water);
            }
            else if(prev == 'W' && curr != 'W'){
                // A new floor
                int j2 = j;
                while(j2<n && grid[i][j2] != 'W') j2++;
                if(j2 != n) memo1 = gid(i,j2,dir), G.connect(gid(i,j,0), memo1, 0);
            }
            else memo1 = -1;
        }
    }

    // Left
    dir = 2;
    for(int i=0; i<n; i++){
        int memo1 = -1;
        int j = n-1;
        while(j>=0 && grid[i][j] == 'W') j--;
        for(; j>=0; j--){
            char prev = j==n-1? 'W':grid[i][j+1];
            char curr = grid[i][j];
            if(prev != 'W' && curr != 'W' && memo1 != -1) G.connect(gid(i,j,0), memo1, 0); // Same wall
            else if(prev != 'W' && curr == 'W'){
                // A new wall
                memo1 = -1;
                int j2 = j, water = 0;
                while(j2>=0 && grid[i][j2] == 'W') j2--, water++;
                for(; j2>=0 && grid[i][j2] != 'W'; j2--) G.connect(gid(i,j,dir), gid(i,j2,dir), water*water);
            }
            else if(prev == 'W' && curr != 'W'){
                // A new floor
                int j2 = j;
                while(j2>=0 && grid[i][j2] != 'W') j2--;
                if(j2 != -1) memo1 = gid(i,j2,dir), G.connect(gid(i,j,0), memo1, 0);
            }
            else memo1 = -1;
        }
    }

    // Down
    dir = 3;
    for(int j=0; j<n; j++){
        int memo1 = -1;
        int i = 0;
        while(i<n && grid[i][j] == 'W') i++;
        for(; i<n; i++){
            char prev = i==0? 'W':grid[i-1][j];
            char curr = grid[i][j];
            if(prev != 'W' && curr != 'W' && memo1 != -1) G.connect(gid(i,j,0), memo1, 0); // Same wall
            else if(prev != 'W' && curr == 'W'){
                // A new wall
                memo1 = -1;
                int i2 = i, water = 0;
                while(i2<n && grid[i2][j] == 'W') i2++, water++;
                for(; i2<n && grid[i2][j] != 'W'; i2++) G.connect(gid(i,j,dir), gid(i2,j,dir), water*water);
            }
            else if(prev == 'W' && curr != 'W'){
                // A new floor
                int i2 = i;
                while(i2<n && grid[i2][j] != 'W') i2++;
                if(i2 != n) memo1 = gid(i2,j,dir), G.connect(gid(i,j,0), memo1, 0);
            }
            else memo1 = -1;
        }
    }

    // Up
    dir = 4;
    for(int j=0; j<n; j++){
        int memo1 = -1;
        int i = n-1;
        while(i>=0 && grid[i][j] == 'W') i--;
        for(; i>=0; i--){
            char prev = i==n-1? 'W':grid[i+1][j];
            char curr = grid[i][j];
            if(prev != 'W' && curr != 'W' && memo1 != -1) G.connect(gid(i,j,0), memo1, 0); // Same wall
            else if(prev != 'W' && curr == 'W'){
                // A new wall
                memo1 = -1;
                int i2 = i, water = 0;
                while(i2>=0 && grid[i2][j] == 'W') i2--, water++;
                for(; i2>=0 && grid[i2][j] != 'W'; i2--) G.connect(gid(i,j,dir), gid(i2,j,dir), water*water);
            }
            else if(prev == 'W' && curr != 'W'){
                // A new floor
                int i2 = i;
                while(i2>=0 && grid[i2][j] != 'W') i2--;
                if(i2 != -1) memo1 = gid(i2,j,dir), G.connect(gid(i,j,0), memo1, 0);
            }
            else memo1 = -1;
        }
    }

    ll ans = G.dijkstra(gid(si,sj,0), gid(ei,ej,0));
    cout << (ans != INF? ans : -1);
}

Compilation message

aqua.cpp: In function 'int main()':
aqua.cpp:18:18: warning: 'ej' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return 5*(n*i+j)+dir;
              ~~~~^~~
aqua.cpp:64:21: note: 'ej' was declared here
     int si, sj, ei, ej;
                     ^~
aqua.cpp:18:16: warning: 'ei' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return 5*(n*i+j)+dir;
               ~^~
aqua.cpp:64:17: note: 'ei' was declared here
     int si, sj, ei, ej;
                 ^~
aqua.cpp:18:18: warning: 'sj' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return 5*(n*i+j)+dir;
              ~~~~^~~
aqua.cpp:64:13: note: 'sj' was declared here
     int si, sj, ei, ej;
             ^~
aqua.cpp:18:16: warning: 'si' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return 5*(n*i+j)+dir;
               ~^~
aqua.cpp:64:9: note: 'si' was declared here
     int si, sj, ei, ej;
         ^~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 692 KB Output is correct
4 Correct 6 ms 1740 KB Output is correct
5 Correct 6 ms 2660 KB Output is correct
6 Correct 13 ms 3216 KB Output is correct
7 Correct 24 ms 3900 KB Output is correct
8 Correct 25 ms 3900 KB Output is correct
9 Correct 18 ms 3900 KB Output is correct
10 Correct 4 ms 3900 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 692 KB Output is correct
4 Correct 6 ms 1740 KB Output is correct
5 Correct 6 ms 2660 KB Output is correct
6 Correct 13 ms 3216 KB Output is correct
7 Correct 24 ms 3900 KB Output is correct
8 Correct 25 ms 3900 KB Output is correct
9 Correct 18 ms 3900 KB Output is correct
10 Correct 4 ms 3900 KB Output is correct
11 Correct 308 ms 36296 KB Output is correct
12 Correct 704 ms 114224 KB Output is correct
13 Correct 2037 ms 181000 KB Output is correct
14 Correct 1476 ms 181000 KB Output is correct
15 Correct 367 ms 188628 KB Output is correct
16 Correct 2944 ms 257836 KB Output is correct
17 Execution timed out 3036 ms 257836 KB Time limit exceeded
18 Halted 0 ms 0 KB -