oj.uz

Submission #129715

# Submission time Handle Problem Language Result Execution time Memory
129715 2019-07-13T05:34:52 Z 송준혁(#3142) 물병 (JOI14_bottle) C++14
100 / 100
 4451 ms 263304 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], D[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);
    memset(D, 1, sizeof D);
    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]);
    chk[0] = true;
    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 || D[T.x][T.y] <= T.w) continue;
            D[T.x][T.y] = T.w;
            if (!chk[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;
            }
            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:40:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf(" %c", &ch);
             ~~~~~^~~~~~~~~~~~
bottle.cpp:45: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:48: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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 222428 KB Output is correct
2 Correct 210 ms 222300 KB Output is correct
3 Correct 223 ms 222300 KB Output is correct
4 Correct 370 ms 240316 KB Output is correct
5 Correct 366 ms 239584 KB Output is correct
6 Correct 361 ms 240112 KB Output is correct
7 Correct 360 ms 240388 KB Output is correct
8 Correct 366 ms 240044 KB Output is correct
9 Correct 368 ms 241204 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 222360 KB Output is correct
2 Correct 440 ms 222972 KB Output is correct
3 Correct 2728 ms 222948 KB Output is correct
4 Correct 3266 ms 223880 KB Output is correct
5 Correct 3735 ms 224628 KB Output is correct
6 Correct 2653 ms 222852 KB Output is correct
7 Correct 3289 ms 223760 KB Output is correct
8 Correct 3509 ms 224680 KB Output is correct
9 Correct 3910 ms 224616 KB Output is correct
10 Correct 3160 ms 223220 KB Output is correct
11 Correct 3172 ms 223612 KB Output is correct
12 Correct 2148 ms 223124 KB Output is correct
13 Correct 2173 ms 222768 KB Output is correct
14 Correct 2139 ms 223092 KB Output is correct
15 Correct 2240 ms 222816 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 222424 KB Output is correct
2 Correct 462 ms 222612 KB Output is correct
3 Correct 2602 ms 223808 KB Output is correct
4 Correct 3406 ms 224680 KB Output is correct
5 Correct 3735 ms 225140 KB Output is correct
6 Correct 3922 ms 225576 KB Output is correct
7 Correct 3175 ms 223868 KB Output is correct
8 Correct 3223 ms 225728 KB Output is correct
9 Correct 2209 ms 225284 KB Output is correct
10 Correct 2245 ms 224876 KB Output is correct
11 Correct 2084 ms 224780 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2964 ms 247392 KB Output is correct
2 Correct 3528 ms 252136 KB Output is correct
3 Correct 3294 ms 224504 KB Output is correct
4 Correct 4162 ms 257964 KB Output is correct
5 Correct 4451 ms 263304 KB Output is correct
6 Correct 3528 ms 249200 KB Output is correct
7 Correct 3161 ms 224372 KB Output is correct
8 Correct 2185 ms 224256 KB Output is correct
9 Correct 3744 ms 260376 KB Output is correct
10 Correct 2934 ms 252592 KB Output is correct
11 Correct 3834 ms 255880 KB Output is correct
12 Correct 3444 ms 253344 KB Output is correct