oj.uz

Submission #594873

# Submission time Handle Problem Language Result Execution time Memory
594873 2022-07-13T05:46:47 Z 반딧불(#8437) 물병 (JOI14_bottle) C++14
100 / 100
 1356 ms 113388 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int xx[]={0, 1, 0, -1}, yy[]={1, 0, -1, 0};

struct unionFind{
    int par[200002];
    unionFind(){}

    void init(int n){
        for(int i=0; i<=n; i++){
            par[i] = i;
        }
    }

    int find(int x){
        if(x == par[x]) return x;
        return par[x] = find(par[x]);
    }

    void merge(int x, int y){
        x = find(x), y = find(y);
        par[x] = y;
    }
} dsu;

struct dat{
    int x, y, d, id;
    dat(){}
    dat(int x, int y, int d, int id): x(x), y(y), d(d), id(id){}
};

struct Edge{
    int x, y, d;
    Edge(){}
    Edge(int x, int y, int d): x(x), y(y), d(d){}
    bool operator<(const Edge &r)const{
        return d<r.d;
    }
};

int n, m, k, q;
char board[2002][2002];
int num[2002][2002];
int px[200002], py[200002];
int dist[2002][2002];
int vnum[2002][2002];
int ans[200002];
int isPlace[2002][2002];
vector<Edge> edges;

void makeEdges(){
    vector<dat> que;
    for(int i=1; i<=k; i++){
        int x = px[i], y = py[i];
        que.push_back(dat(x, y, 0, i));
        dist[x][y] = 0;
        vnum[x][y] = i;
    }
    while(!que.empty()){
        int len = que.front().d;
        vector<dat> nqueue;
        vector<Edge> waitlist;

        while(!que.empty()){
            dat tmp = que.back(); que.pop_back();
            int x = tmp.x, y = tmp.y;
//            printf("(%d, %d, %d, %d)\n", x, y, len, tmp.id);
            for(int d=0; d<4; d++){
                int tx = x+xx[d], ty = y+yy[d];
                if(tx<1 || tx>n || ty<1 || ty>m || board[tx][ty]=='#' || dist[tx][ty]<len) continue;
                if(dist[tx][ty] == 1e9){
                    dist[tx][ty] = len+1;
                    vnum[tx][ty] = tmp.id;
                    nqueue.push_back(dat(tx, ty, len+1, tmp.id));
                }
                else if(!vnum[tx][ty]) continue;
                else{ /// �ٷ� ���� ��
                    int vx = tmp.id, vy = vnum[tx][ty];
                    if(dsu.find(vx) == dsu.find(vy)) continue;
                    if(dist[tx][ty] == len){
                        dsu.merge(vx, vy);
                        edges.push_back(Edge(vx, vy, len*2));
                    }
                    else{
                        assert(dist[tx][ty] == len+1);
                        waitlist.push_back(Edge(vx, vy, len*2+1));
                    }
                }
            }
        }

        for(Edge edge: waitlist){
            if(dsu.find(edge.x) == dsu.find(edge.y)) continue;
            dsu.merge(edge.x, edge.y);
            edges.push_back(Edge(edge.x, edge.y, edge.d));
        }

        que.swap(nqueue);
    }
}

int ql[200002], qr[200002];
int pbsL[200002], pbsR[200002], pbsMid[200002], pbsAns[200002];
vector<int> pbsVec[200002];
int pbsDone;

int main(){
    scanf("%d %d %d %d", &n, &m, &k, &q);
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
        scanf(" %c", &board[i][j]);
        num[i][j] = (i-1)*m+j;
        dist[i][j] = 1e9;
    }
    for(int i=1; i<=k; i++){
        scanf("%d %d", &px[i], &py[i]);
        board[px[i]][py[i]] = 'b';
        dist[px[i]][py[i]] = 0;
        isPlace[px[i]][py[i]] = i;
    }
    dsu.init(k);

    makeEdges();
    int s = (int)edges.size();
    sort(edges.begin(), edges.end());

    for(int i=1; i<=q; i++){
        scanf("%d %d", &ql[i], &qr[i]);
        pbsL[i] = 0, pbsR[i] = s-1, pbsAns[i] = s;
        if(pbsL[i] > pbsR[i]) pbsDone++;
    }
    while(pbsDone < q){
        for(int i=0; i<s; i++) pbsVec[i].clear();
        for(int i=1; i<=q; i++){
            if(pbsL[i] > pbsR[i]) continue;
            pbsMid[i] = (pbsL[i] + pbsR[i]) / 2;
            pbsVec[pbsMid[i]].push_back(i);
        }
        dsu.init(k);
        for(int i=0; i<s; i++){
            dsu.merge(edges[i].x, edges[i].y);
            for(auto x: pbsVec[i]){
                if(dsu.find(ql[x]) == dsu.find(qr[x])){
                    pbsAns[x] = i;
                    pbsR[x] = i-1;
                }
                else pbsL[x] = i+1;
                if(pbsL[x] > pbsR[x]) pbsDone++;
            }
        }
    }

    for(int i=1; i<=q; i++){
        if(pbsAns[i] == s) puts("-1");
        else printf("%d\n", edges[pbsAns[i]].d);
    }
}

Compilation message

bottle.cpp: In function 'int main()':
bottle.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |     scanf("%d %d %d %d", &n, &m, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         scanf(" %c", &board[i][j]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
bottle.cpp:118:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         scanf("%d %d", &px[i], &py[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:130:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         scanf("%d %d", &ql[i], &qr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6356 KB Output is correct
2 Correct 7 ms 8660 KB Output is correct
3 Correct 9 ms 8964 KB Output is correct
4 Correct 89 ms 20992 KB Output is correct
5 Correct 104 ms 20536 KB Output is correct
6 Correct 101 ms 20928 KB Output is correct
7 Correct 91 ms 21052 KB Output is correct
8 Correct 98 ms 21152 KB Output is correct
9 Correct 102 ms 22436 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 38900 KB Output is correct
2 Correct 48 ms 13572 KB Output is correct
3 Correct 479 ms 70296 KB Output is correct
4 Correct 545 ms 73224 KB Output is correct
5 Correct 596 ms 75444 KB Output is correct
6 Correct 474 ms 70240 KB Output is correct
7 Correct 551 ms 73368 KB Output is correct
8 Correct 630 ms 75556 KB Output is correct
9 Correct 627 ms 80504 KB Output is correct
10 Correct 490 ms 59496 KB Output is correct
11 Correct 558 ms 65968 KB Output is correct
12 Correct 339 ms 54444 KB Output is correct
13 Correct 327 ms 61680 KB Output is correct
14 Correct 348 ms 56224 KB Output is correct
15 Correct 353 ms 61468 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 38896 KB Output is correct
2 Correct 47 ms 12380 KB Output is correct
3 Correct 398 ms 58752 KB Output is correct
4 Correct 561 ms 73060 KB Output is correct
5 Correct 616 ms 75528 KB Output is correct
6 Correct 604 ms 80852 KB Output is correct
7 Correct 477 ms 59680 KB Output is correct
8 Correct 554 ms 73164 KB Output is correct
9 Correct 328 ms 56616 KB Output is correct
10 Correct 386 ms 61912 KB Output is correct
11 Correct 360 ms 65996 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 87704 KB Output is correct
2 Correct 985 ms 99784 KB Output is correct
3 Correct 472 ms 60052 KB Output is correct
4 Correct 1169 ms 107892 KB Output is correct
5 Correct 1356 ms 113388 KB Output is correct
6 Correct 730 ms 91432 KB Output is correct
7 Correct 532 ms 59924 KB Output is correct
8 Correct 354 ms 53900 KB Output is correct
9 Correct 1063 ms 96540 KB Output is correct
10 Correct 838 ms 99940 KB Output is correct
11 Correct 1048 ms 113204 KB Output is correct
12 Correct 917 ms 102016 KB Output is correct