oj.uz

Submission #129708

# Submission time Handle Problem Language Result Execution time Memory
129708 2019-07-13T05:18:12 Z 송준혁(#3142) 물병 (JOI14_bottle) C++14
0 / 100
 2603 ms 230020 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, Q, H, W, cnt;
int M[2020][2020];
int X[202020], Y[202020];
int U[202020], V[202020], P[202020];
int L[202020], R[202020], ans[202020];
bool chk[202020];
vector<int> PBS[4040404], tmp[4040404];

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

struct Data{
    int x, y;
    int d, w;
    bool operator<(const Data&r)const{
        return w > r.w;
    }
};
vector<Data> E;
priority_queue<Data> PQ;


int Find(int u){
    if (P[u] == u) return u;
    return P[u] = Find(P[u]);
}

int main(){
    scanf("%d %d %d %d", &H, &W, &N, &Q);
    memset(M, -1, sizeof M);
    for (int i=1; i<=H; i++){
        for (int j=1; j<=W; j++){
            char ch;
            scanf(" %c", &ch);
            if (ch == '.') M[i][j] = 0;
        }
    }
    for (int i=1; i<=N; i++) {
        scanf("%d %d", &X[i], &Y[i]);
        M[X[i]][Y[i]] = i;
    }
    for (int i=1; i<=Q; i++) scanf("%d %d", &U[i], &V[i]);
    for (int k=1; k<=N; k++){
        if (chk[k]) continue;
        PQ.push((Data){X[k], Y[k], 0, 0});
        while (!PQ.empty()){
            Data T = PQ.top();
            PQ.pop();
            if (M[T.x][T.y] == -1) continue;
            if (M[T.x][T.y]){
                if (T.d) E.push_back((Data){T.d, M[T.x][T.y], 0, T.w-1});
                T.d = M[T.x][T.y], T.w = 0;
                chk[M[T.x][T.y]] = true;
            }
            M[T.x][T.y] = -1;
            for (int i=0; i<4; i++) PQ.push((Data){T.x+dx[i], T.y+dy[i], T.d, T.w+1});
        }
    }
    sort(E.begin(), E.end(), [&](Data a, Data b){return a.w < b.w;});
    for (int i=1; i<=Q; i++) {
        L[i] = 0, R[i] = H*W, ans[i] = -1;
        PBS[(L[i]+R[i])/2].push_back(i);
    }
    while (cnt<Q){
        for (int i=1; i<=N; i++) P[i] = i;
        int t=0;
        for (Data e : E){
            while (e.w > t){
                for (int x : PBS[t]){
                    if (Find(U[x]) == Find(V[x])) ans[x] = (L[x]+R[x])/2, R[x] = (L[x]+R[x])/2-1;
                    else L[x] = (L[x]+R[x])/2+1;
                }
                t++;
            }
            P[Find(e.x)] = Find(e.y);
        }
        while (t<=H*W){
            for (int x : PBS[t]){
                if (Find(U[x]) == Find(V[x])) ans[x] = (L[x]+R[x])/2, R[x] = (L[x]+R[x])/2-1;
                else L[x] = (L[x]+R[x])/2+1;
            }
            t++;
        }
        for (int i=0; i<=H*W; i++){
            for (int x : PBS[i]) {
                if (L[x] > R[x]){
                    cnt++;
                    continue;
                }
                tmp[(L[x]+R[x])/2].push_back(x);
            }
            PBS[i].clear();
        }
        for (int i=0; i<=H*W; i++) swap(PBS[i], tmp[i]);
    }
    for (int i=1; i<=Q; i++) printf("%d\n", ans[i]);
    return 0;
}
/*
5 5 4 4
.....
..##.
.#...
..#..
.....
1 1
4 2
3 3
2 5
1 2
2 4
1 3
3 4

5 5 3 2
...#.
..#..
#....
.##..
...#.
1 3
5 2
1 5
1 2
1 3
*/

Compilation message

bottle.cpp: In function 'int main()':
bottle.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d", &H, &W, &N, &Q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:39:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c", &ch);
             ~~~~~^~~~~~~~~~~~
bottle.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &X[i], &Y[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:47:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i=1; i<=Q; i++) scanf("%d %d", &U[i], &V[i]);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 195 ms 206328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 274 ms 206316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 278 ms 206328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2603 ms 230020 KB Output isn't correct
2 Halted 0 ms 0 KB -