oj.uz

Submission #72104

# Submission time Handle Problem Language Result Execution time Memory
72104 2018-08-26T05:17:56 Z 신딩없는 신딩팀(#2212, willi19, andy627, maruii) Aquatic Labyrinth (FXCUP3_aqua) C++17
100 / 100
 1430 ms 255112 KB 
#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#define LL long long
#define INF 1e18
using namespace std;

struct xyw{
    LL x,y,w;

    bool operator>(const xyw A)const{
        return w>A.w;
    }
};

bool mp[999][999];
LL dist[999][999];

vector<xyw> edge[999][999];
priority_queue<xyw,vector<xyw>,greater<xyw> > pq;

vector<int> st;

int main(){
    int n;
    int sx,sy,ex,ey;

    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            char c;
            scanf(" %c",&c);

            if(c=='W') mp[i][j]=1;
            if(c=='H') ex=i,ey=j;
            if(c=='M') sx=i,sy=j;
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int pos=i+1,cnt=0;
            while(pos<=n && !mp[pos][j]) pos++;
            while(pos<=n && mp[pos][j]) pos++,cnt++;
            while(pos<=n && !mp[pos][j]) edge[i][j].push_back({pos++,j,cnt*cnt});

            pos=i-1,cnt=0;
            while(pos>0 && !mp[pos][j]) pos--;
            while(pos>0 && mp[pos][j]) pos--,cnt++;
            while(pos>0 && !mp[pos][j]) edge[i][j].push_back({pos--,j,cnt*cnt});

            pos=j+1,cnt=0;
            while(pos<=n && !mp[i][pos]) pos++;
            while(pos<=n && mp[i][pos]) pos++,cnt++;
            while(pos<=n && !mp[i][pos]) edge[i][j].push_back({i,pos++,cnt*cnt});

            pos=j-1,cnt=0;
            while(pos>0 && !mp[i][pos]) pos--;
            while(pos>0 && mp[i][pos]) pos--,cnt++;
            while(pos>0 && !mp[i][pos]) edge[i][j].push_back({i,pos--,cnt*cnt});
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) dist[i][j]=INF;
    }
    dist[sx][sy]=0;

    pq.push({sx,sy,0});
    while(!pq.empty()){
        int px=pq.top().x;
        int py=pq.top().y;
        int pw=pq.top().w;
        pq.pop();

        if(px==ex && py==ey){
            printf("%lld",dist[ex][ey]);
            return 0;
        }
        if(pw!=dist[px][py]) continue;

        for(xyw it:edge[px][py]){
            if(dist[it.x][it.y]>dist[px][py]+it.w){
                dist[it.x][it.y]=dist[px][py]+it.w;
                pq.push({it.x,it.y,dist[it.x][it.y]});
            }
        }
    }

    printf("-1");

    return 0;
}

Compilation message

aqua.cpp: In function 'int main()':
aqua.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
aqua.cpp:33:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c",&c);
             ~~~~~^~~~~~~~~~
aqua.cpp:78:19: warning: 'ex' may be used uninitialized in this function [-Wmaybe-uninitialized]
             printf("%lld",dist[ex][ey]);
             ~~~~~~^~~~~~~~~~~~~~~~~~~~~
aqua.cpp:70:12: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
     pq.push({sx,sy,0});
     ~~~~~~~^~~~~~~~~~~
aqua.cpp:78:19: warning: 'ey' may be used uninitialized in this function [-Wmaybe-uninitialized]
             printf("%lld",dist[ex][ey]);
             ~~~~~~^~~~~~~~~~~~~~~~~~~~~
aqua.cpp:70:12: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
     pq.push({sx,sy,0});
     ~~~~~~~^~~~~~~~~~~

Subtask #1
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23672 KB Output is correct
2 Correct 31 ms 24168 KB Output is correct
3 Correct 29 ms 24168 KB Output is correct
4 Correct 31 ms 25168 KB Output is correct
5 Correct 25 ms 25168 KB Output is correct
6 Correct 32 ms 27048 KB Output is correct
7 Correct 35 ms 27288 KB Output is correct
8 Correct 35 ms 27340 KB Output is correct
9 Correct 42 ms 27340 KB Output is correct
10 Correct 32 ms 27340 KB Output is correct

Subtask #2
64.0 / 64.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 23672 KB Output is correct
2 Correct 31 ms 24168 KB Output is correct
3 Correct 29 ms 24168 KB Output is correct
4 Correct 31 ms 25168 KB Output is correct
5 Correct 25 ms 25168 KB Output is correct
6 Correct 32 ms 27048 KB Output is correct
7 Correct 35 ms 27288 KB Output is correct
8 Correct 35 ms 27340 KB Output is correct
9 Correct 42 ms 27340 KB Output is correct
10 Correct 32 ms 27340 KB Output is correct
11 Correct 130 ms 56680 KB Output is correct
12 Correct 199 ms 68180 KB Output is correct
13 Correct 706 ms 185084 KB Output is correct
14 Correct 524 ms 203824 KB Output is correct
15 Correct 1345 ms 203824 KB Output is correct
16 Correct 932 ms 254388 KB Output is correct
17 Correct 1012 ms 255112 KB Output is correct
18 Correct 454 ms 255112 KB Output is correct
19 Correct 762 ms 255112 KB Output is correct
20 Correct 1430 ms 255112 KB Output is correct