oj.uz

답안 #594862

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
594862 2022-07-13T05:36:14 Z 반딧불(#8437) 물병 (JOI14_bottle) C++14
0 / 100
 591 ms 73148 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 = par[x], y = par[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];
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;
    }
    dsu.init(k);

    makeEdges();
    int s = (int)edges.size();

    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:110:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |     scanf("%d %d %d %d", &n, &m, &k, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:112:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         scanf(" %c", &board[i][j]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
bottle.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         scanf("%d %d", &px[i], &py[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:127:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |         scanf("%d %d", &ql[i], &qr[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 6100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 36 ms 35732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 35788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 591 ms 73148 KB Output isn't correct
2 Halted 0 ms 0 KB -