제출 #14632

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

bottle

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int,int> pi;

struct edg{int s,e,x;};
vector<edg> tree;
vector<pi> graph[200005];

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

int n,m,p,q;
char str[2005][2005];
int reg[2005][2005], dist[2005][2005];
int pa[200005][18], val[200005][18], dep[200005];

struct disj{
    int pa[200005];
    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;
        pa[p] = q;
        return 1;
    }
}disj;

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

int qr(int s, int e){
    if(dep[s] > dep[e]) swap(s,e);
    int ret = 0, dx = dep[e] - dep[s];
    for (int i=0; (1<<i)<=dx; i++) {
        if(dx & (1<<i)){
            ret = max(ret,val[e][i]);
            e = pa[e][i];
        }
    }
    for (int i=17; i>=0; i--) {
        if(pa[s][i] != pa[e][i]){
            ret = max(ret,val[s][i]);
            ret = max(ret,val[e][i]);
            s = pa[s][i];
            e = pa[e][i];
        }
    }
    if(s != e){
        ret = max(ret,val[s][0]);
        ret = max(ret,val[e][0]);
    }
    return ret;
}

vector<edg> cand;
queue<int> qx,qy;

void make_tree(){
    for (int i=1; i<=p; i++) {
        int px,py;
        scanf("%d %d",&px,&py);
        px--;
        py--;
        qx.push(px);
        qy.push(py);
        reg[px][py] = i;
        dist[px][py] = 0;
    }
    while (!qx.empty()) {
        int xf = qx.front();
        int yf = qy.front();
        qx.pop();
        qy.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(reg[xf+dx[i]][yf+dy[i]]) continue;
            reg[xf+dx[i]][yf+dy[i]] = reg[xf][yf];
            dist[xf+dx[i]][yf+dy[i]] = dist[xf][yf] +1;
            qx.push(xf + dx[i]);
            qy.push(yf + dy[i]);
        }
    }
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            if(j + 1 != m && reg[i][j] != reg[i][j+1] && reg[i][j] && reg[i][j+1]){
                cand.push_back({reg[i][j],reg[i][j+1],dist[i][j] + dist[i][j+1]});
            }
            if(i + 1 != n && reg[i][j] != reg[i+1][j] && reg[i][j] && reg[i+1][j]){
                cand.push_back({reg[i][j],reg[i+1][j],dist[i][j] + dist[i+1][j]});
            }
        }
    }
    sort(cand.begin(),cand.end(),cmp);
    for (int i=0; i<cand.size(); i++) {
        if(disj.uni(cand[i].s,cand[i].e)){
            graph[cand[i].s].push_back(pi(cand[i].x,cand[i].e));
            graph[cand[i].e].push_back(pi(cand[i].x,cand[i].s));
        }
    }
    for (int i=1; i<p; i++) {
        if(disj.uni(i,i+1)){
            graph[i].push_back(pi(1e9,i+1));
            graph[i+1].push_back(pi(1e9,i));
        }
    }
}

void process_tree(){
    qx.push(1);
    qy.push(0);
    while (!qx.empty()) {
        int xf = qx.front();
        int yf = qy.front();
        qx.pop();
        qy.pop();
        for (int i=1; (1<<i) <= dep[xf]; i++) {
            pa[xf][i] = pa[pa[xf][i-1]][i-1];
            val[xf][i] = max(val[xf][i-1],val[pa[xf][i-1]][i-1]);
        }
        for (int i=0; i<graph[xf].size(); i++) {
            int pos = graph[xf][i].second;
            if(pos != yf){
                pa[pos][0] = xf;
                val[pos][0] = graph[xf][i].first;
                dep[pos] = dep[xf] + 1;
                qx.push(pos);
                qy.push(xf);
            }
        }
    }
}

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();
    process_tree();
    for (int i=0; i<q; i++) {
        int s,e;
        scanf("%d %d",&s,&e);
        int ret = qr(s,e);
        if(ret > 1e8) puts("-1");
        else printf("%d\n",ret);
    }
}

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