oj.uz

Submission #594918

# Submission time Handle Problem Language Result Execution time Memory
594918 2022-07-13T07:08:07 Z 이동현(#8440) 물병 (JOI14_bottle) C++14
100 / 100
 1480 ms 189060 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;
    auto doans = [&](vector<pair<int, int>>&u, int pl)->void{
        for(auto&i:u){
            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] = (lst + 1) * 2 - 1 + pl;
                }
                else{
                    ask[i.second].push_back(j);
                }
            }
            for(auto&j:who[i.first]){
                who[i.second].insert(j);
            }
        }
    };
    while(f < r){
        int x = que[f][0], y = que[f][1], c = que[f][2], dis = que[f][3];
        ++f;
        if(dis > lst){
            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});
                }
            }
        }
    }
    doans(u1, -1);
    doans(u2, 0);
    for(int i = 1; i <= q; ++i){
        if(ans[i] == (int)1e9){
            ans[i] = -1;
        }
        cout << ans[i] << '\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15444 KB Output is correct
2 Correct 10 ms 16852 KB Output is correct
3 Correct 12 ms 17364 KB Output is correct
4 Correct 83 ms 29828 KB Output is correct
5 Correct 86 ms 30516 KB Output is correct
6 Correct 82 ms 30228 KB Output is correct
7 Correct 78 ms 29196 KB Output is correct
8 Correct 79 ms 30724 KB Output is correct
9 Correct 95 ms 31912 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 38548 KB Output is correct
2 Correct 57 ms 27132 KB Output is correct
3 Correct 339 ms 84044 KB Output is correct
4 Correct 469 ms 97264 KB Output is correct
5 Correct 568 ms 105020 KB Output is correct
6 Correct 394 ms 85648 KB Output is correct
7 Correct 507 ms 96616 KB Output is correct
8 Correct 516 ms 104656 KB Output is correct
9 Correct 604 ms 118204 KB Output is correct
10 Correct 452 ms 94156 KB Output is correct
11 Correct 482 ms 94672 KB Output is correct
12 Correct 162 ms 85068 KB Output is correct
13 Correct 219 ms 81180 KB Output is correct
14 Correct 176 ms 83160 KB Output is correct
15 Correct 213 ms 81112 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 38356 KB Output is correct
2 Correct 38 ms 22548 KB Output is correct
3 Correct 260 ms 80604 KB Output is correct
4 Correct 511 ms 96088 KB Output is correct
5 Correct 546 ms 103480 KB Output is correct
6 Correct 611 ms 115396 KB Output is correct
7 Correct 429 ms 95008 KB Output is correct
8 Correct 460 ms 95740 KB Output is correct
9 Correct 167 ms 81264 KB Output is correct
10 Correct 224 ms 81660 KB Output is correct
11 Correct 196 ms 77764 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 100588 KB Output is correct
2 Correct 1114 ms 155400 KB Output is correct
3 Correct 474 ms 94828 KB Output is correct
4 Correct 1343 ms 168944 KB Output is correct
5 Correct 1480 ms 179012 KB Output is correct
6 Correct 687 ms 117448 KB Output is correct
7 Correct 417 ms 94276 KB Output is correct
8 Correct 147 ms 79384 KB Output is correct
9 Correct 1260 ms 178400 KB Output is correct
10 Correct 1177 ms 178408 KB Output is correct
11 Correct 1196 ms 189060 KB Output is correct
12 Correct 1158 ms 183552 KB Output is correct