oj.uz

Submission #594868

# Submission time Handle Problem Language Result Execution time Memory
594868 2022-07-13T05:40:40 Z 이동현(#8440) 물병 (JOI14_bottle) C++14
0 / 100
 521 ms 99140 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] == dis){
                    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 Incorrect 9 ms 15444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

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