oj.uz

Submission #595013

# Submission time Handle Problem Language Result Execution time Memory
595013 2022-07-13T09:00:24 Z 박상훈(#8436) 물병 (JOI14_bottle) C++14
10 / 100
 284 ms 36772 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct Vertex{
    int x, y, d;
    Vertex(){}
    Vertex(int _x, int _y, int _d): x(_x), y(_y), d(_d) {}
};
char buf[2020];
int dist[202][202], a[2020][2020], X[200200], Y[200200], visited[2020][2020];
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};

void bfs(int x, int y, int s, int d){
    queue<Vertex> q;
    q.emplace(x, y, d);
    visited[x][y] = 1;

    while(!q.empty()){
        auto [x, y, d] = q.front(); q.pop();
        if (a[x][y]>0){
            dist[s][a[x][y]] = min(dist[s][a[x][y]], d);
            dist[a[x][y]][s] = min(dist[a[x][y]][s], d);
        }

        for (int k=0;k<4;k++){
            int nx = x + dx[k], ny = y + dy[k];
            if (!visited[nx][ny] && a[nx][ny]!=-1){
                q.emplace(nx, ny, d+1);
                visited[nx][ny] = 1;
            }
        }
    }


}

int main(){
    int n, m, p, q;
    scanf("%d %d %d %d", &n, &m, &p, &q);

    for (int i=0;i<=n+1;i++) fill(a[i], a[i]+m+2, -1);

    for (int i=1;i<=n;i++){
        scanf("%s", buf+1);
        for (int j=1;j<=m;j++) a[i][j] = buf[j]=='.'?0:-1;
    }

    //printf("YES\n");

    for (int i=1;i<=p;i++){
        scanf("%d %d", X+i, Y+i);
        a[X[i]][Y[i]] = i;
    }

    for (int i=1;i<=p;i++) fill(dist[i]+1, dist[i]+p+1, 1e9);
    for (int i=1;i<=p;i++){
        for (int j=1;j<=n;j++) fill(visited[j]+1, visited[j]+m+1, 0);
        bfs(X[i], Y[i], i, 0);
    }

    for (int mid=1;mid<=p;mid++){
        for (int s=1;s<=p;s++){
            for (int e=1;e<=p;e++){
                dist[s][e] = min(dist[s][e], max(dist[s][mid], dist[mid][e]));
            }
        }
    }

    for (int i=1;i<=q;i++){
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%d\n", dist[x][y]==1e9?-1:dist[x][y]-1);
    }
    return 0;
}

Compilation message

bottle.cpp: In function 'void bfs(int, int, int, int)':
bottle.cpp:20:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |         auto [x, y, d] = q.front(); q.pop();
      |              ^
bottle.cpp: In function 'int main()':
bottle.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d %d %d %d", &n, &m, &p, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%s", buf+1);
      |         ~~~~~^~~~~~~~~~~~~
bottle.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%d %d", X+i, Y+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
bottle.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 1108 KB Output is correct
2 Correct 90 ms 2216 KB Output is correct
3 Correct 243 ms 2456 KB Output is correct
4 Correct 276 ms 4300 KB Output is correct
5 Correct 284 ms 4312 KB Output is correct
6 Correct 191 ms 4300 KB Output is correct
7 Correct 205 ms 4304 KB Output is correct
8 Correct 138 ms 4500 KB Output is correct
9 Correct 120 ms 4556 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 18840 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 18884 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 44 ms 36772 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -