oj.uz

Submission #594870

# Submission time Handle Problem Language Result Execution time Memory
594870 2022-07-13T05:43:14 Z 이동현(#8440) 물병 (JOI14_bottle) C++14
30 / 100
 1516 ms 185428 KB 
#include <bits/stdc++.h>

using namespace std;

const int NS = (int)2e5 + 4;

struct DSU{
    int n;
    vector<int> pr;
    DSU(){}
    DSU(int n):n(n + 4){
        pr.resize(n);
        for(int i = 0; i < n; ++i){
            pr[i] = i;
        }
    }
    int fd(int x){
        return (pr[x] == x ? x : pr[x] = fd(pr[x]));
    }
    bool unite(int x, int y){
        x = fd(x), y = fd(y);
        if(x == y) return false;
        pr[x] = y;
        return true;
    }
};

int n, m, p, q;
char s[2004][2004];
int ans[NS];
pair<int, int> tower[NS];
vector<pair<int, int>> ask[NS];
set<int> who[NS];
int que[2004 * 2004][4], f, r, col[2004][2004], cdis[2004][2004];
int wx[4] = {-1, 0, 1, 0}, wy[4] = {0, 1, 0, -1};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> p >> q;
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            cin >> s[i][j];
        }
    }
    for(int i = 1; i <= p; ++i){
        cin >> tower[i].first >> tower[i].second;
        que[r][0] = tower[i].first, que[r][1] = tower[i].second, que[r++][2] = i;
        col[tower[i].first][tower[i].second] = i;
        cdis[tower[i].first][tower[i].second] = 1;
        who[i].insert(i);
    }
    for(int i = 1; i <= q; ++i){
        int x, y; cin >> x >> y;
        ask[x].push_back({y, i});
        ask[y].push_back({x, i});
        ans[i] = (int)1e9;
    }
    DSU gr(p + 4);
    int lst = 0;
    vector<pair<int, int>> u1, u2;
    while(f < r){
        int x = que[f][0], y = que[f][1], c = que[f][2], dis = que[f][3];
        ++f;
        if(dis > lst){
            auto doans = [&](vector<pair<int, int>>&u1, int pl)->void{
                for(auto&i:u1){
                    i.first = gr.fd(i.first), i.second = gr.fd(i.second);
                    if(i.first == i.second){
                        continue;
                    }
                    if((int)ask[i.first].size() > (int)ask[i.second].size()){
                        swap(i.first, i.second);
                    }
                    gr.unite(i.first, i.second);
                    for(auto&j:ask[i.first]){
                        auto p = who[i.second].lower_bound(j.first);
                        if(p != who[i.second].end() && *p == j.first){
                            ans[j.second] = dis * 2 - 1 + pl;
                        }
                        else{
                            ask[i.second].push_back(j);
                        }
                    }
                    for(auto&j:who[i.first]){
                        who[i.second].insert(j);
                    }
                }
            };
            doans(u1, -1);
            doans(u2, 0);
            u1.clear(), u2.clear();
            lst = dis;
        }
        for(int i = 0; i < 4; ++i){
            int nx = x + wx[i], ny = y + wy[i];
            if(nx < 1 || nx > n || ny < 1 || ny > m || s[nx][ny] == '#'){
                continue;
            }
            if(!col[nx][ny]){
                col[nx][ny] = c; cdis[nx][ny] = cdis[x][y] + 1;
                que[r][0] = nx, que[r][1] = ny, que[r][2] = c, que[r++][3] = dis + 1;
            }
            else{
                if(gr.fd(col[nx][ny]) == gr.fd(c)){
                    continue;
                }
                if(cdis[nx][ny] == cdis[x][y]){
                    u1.push_back({col[nx][ny], c});
                }
                else{
                    u2.push_back({col[nx][ny], c});
                }
            }
        }
    }
    for(int i = 1; i <= q; ++i){
        if(ans[i] == (int)1e9){
            ans[i] = -1;
        }
        cout << ans[i] << '\n';
    }
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 15444 KB Output is correct
2 Correct 10 ms 16952 KB Output is correct
3 Correct 12 ms 17364 KB Output is correct
4 Correct 77 ms 31196 KB Output is correct
5 Correct 97 ms 31888 KB Output is correct
6 Correct 79 ms 31652 KB Output is correct
7 Correct 78 ms 30432 KB Output is correct
8 Incorrect 76 ms 31516 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 38568 KB Output is correct
2 Correct 58 ms 27480 KB Output is correct
3 Correct 354 ms 86520 KB Output is correct
4 Correct 492 ms 99324 KB Output is correct
5 Correct 529 ms 107192 KB Output is correct
6 Correct 365 ms 87712 KB Output is correct
7 Correct 502 ms 98684 KB Output is correct
8 Correct 534 ms 106868 KB Output is correct
9 Correct 631 ms 120376 KB Output is correct
10 Correct 412 ms 96240 KB Output is correct
11 Correct 464 ms 96828 KB Output is correct
12 Correct 184 ms 87240 KB Output is correct
13 Correct 241 ms 83148 KB Output is correct
14 Correct 169 ms 85368 KB Output is correct
15 Correct 208 ms 83216 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 38348 KB Output is correct
2 Correct 41 ms 22976 KB Output is correct
3 Correct 245 ms 82996 KB Output is correct
4 Correct 518 ms 98400 KB Output is correct
5 Correct 577 ms 105760 KB Output is correct
6 Correct 619 ms 117700 KB Output is correct
7 Correct 442 ms 97228 KB Output is correct
8 Correct 493 ms 98008 KB Output is correct
9 Correct 171 ms 83540 KB Output is correct
10 Incorrect 223 ms 83840 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 98996 KB Output is correct
2 Correct 1145 ms 161724 KB Output is correct
3 Correct 425 ms 96940 KB Output is correct
4 Correct 1357 ms 175164 KB Output is correct
5 Correct 1516 ms 185428 KB Output is correct
6 Correct 724 ms 121788 KB Output is correct
7 Correct 422 ms 96240 KB Output is correct
8 Correct 167 ms 81564 KB Output is correct
9 Incorrect 1176 ms 179436 KB Output isn't correct
10 Halted 0 ms 0 KB -