제출 #13401

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13401		gs14004	물병 (JOI14_bottle)	C++14	70 / 100	5000 ms	335432 KiB

bottle

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

struct edg{int s,e,x;};
vector<edg> tree;

bool cmp(edg a, edg b){
    return a.x < b.x;
}

int n,m,p,q;
char str[2005][2005];
int domain[2005][2005], depth[2005][2005];

struct disj{
    int pa[200005], r;
    void init(int n){
        for(int i=0; i<=n; i++) pa[i] = i;
    }
    int find(int x){
        if(pa[x] == x) return x;
        return pa[x] = find(pa[x]);
    }
    bool uni(int p, int q){
        p = find(p);
        q = find(q);
        if(p == q) return 0;
        if(r&1) pa[p] = q;
        else pa[q] = p;
        r++;
        return 1;
    }
}disj;

int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

void make_tree(){
    vector<edg> cand;
    queue<int> qx,qy,qd,qn;
    for (int i=1; i<=p; i++) {
        int px,py;
        scanf("%d %d",&px,&py);
        px--;
        py--;
        qx.push(px);
        qy.push(py);
        qd.push(0);
        qn.push(i);
        domain[px][py] = i;
        depth[px][py] = 0;
    }
    while (!qx.empty()) {
        int xf = qx.front();
        int yf = qy.front();
        int df = qd.front();
        int nf = qn.front();
        qx.pop();
        qy.pop();
        qd.pop();
        qn.pop();
        for (int i=0; i<4; i++) {
            if(xf + dx[i] < 0 || xf + dx[i] >= n || yf + dy[i] < 0 || yf + dy[i] >= m){
                continue;
            }
            if(str[xf+dx[i]][yf+dy[i]] == '#') continue;
            if(domain[xf+dx[i]][yf+dy[i]]){
                cand.push_back({domain[xf+dx[i]][yf+dy[i]],nf,depth[xf+dx[i]][yf+dy[i]] + df});
                continue;
            }
            domain[xf+dx[i]][yf+dy[i]] = nf;
            depth[xf+dx[i]][yf+dy[i]] = df+1;
            qx.push(xf + dx[i]);
            qy.push(yf + dy[i]);
            qd.push(df + 1);
            qn.push(nf);
        }
    }
    sort(cand.begin(),cand.end(),cmp);
    for (int i=0; i<cand.size(); i++) {
        if(disj.uni(cand[i].s,cand[i].e)){
            tree.push_back(cand[i]);
        }
    }
}

int main(){
    scanf("%d %d %d %d",&n,&m,&p,&q);
    for (int i=0; i<n; i++) {
        scanf("%s",str[i]);
    }
    disj.init(p);
    make_tree();
    for (int i=0; i<q; i++) {
        disj.init(p);
        int s,e;
        scanf("%d %d",&s,&e);
        int nf = 1;
        for (int j=0; j<tree.size(); j++) {
            disj.uni(tree[j].s,tree[j].e);
            if(disj.find(s) == disj.find(e)){
                printf("%d\n",tree[j].x);
                nf = 0;
                break;
            }
        }
        if(nf)puts("-1");
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 0 / 30