oj.uz

Submission #14631

# Submission time Handle Problem Language Result Execution time Memory
14631 2015-05-23T07:58:53 Z gs14004 물병 (JOI14_bottle) C++14
0 / 100
 5000 ms 72236 KB 
#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();
        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;
            }
        }
    }
}

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
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5000 ms 71292 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5000 ms 71700 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5000 ms 71700 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5000 ms 72236 KB Program timed out
2 Halted 0 ms 0 KB -