oj.uz

Submission #14632

# Submission time Handle Problem Language Result Execution time Memory
14632 2015-05-23T07:59:47 Z gs14004 물병 (JOI14_bottle) C++14
100 / 100
 884 ms 111420 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();
        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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 71296 KB Output is correct
2 Correct 4 ms 71296 KB Output is correct
3 Correct 0 ms 71296 KB Output is correct
4 Correct 80 ms 71296 KB Output is correct
5 Correct 71 ms 71296 KB Output is correct
6 Correct 93 ms 71296 KB Output is correct
7 Correct 86 ms 71296 KB Output is correct
8 Correct 99 ms 71500 KB Output is correct
9 Correct 86 ms 71296 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 71700 KB Output is correct
2 Correct 27 ms 72636 KB Output is correct
3 Correct 223 ms 72060 KB Output is correct
4 Correct 343 ms 74336 KB Output is correct
5 Correct 335 ms 76640 KB Output is correct
6 Correct 224 ms 72060 KB Output is correct
7 Correct 337 ms 74264 KB Output is correct
8 Correct 354 ms 76644 KB Output is correct
9 Correct 346 ms 81956 KB Output is correct
10 Correct 252 ms 72632 KB Output is correct
11 Correct 271 ms 73964 KB Output is correct
12 Correct 125 ms 73968 KB Output is correct
13 Correct 131 ms 71972 KB Output is correct
14 Correct 118 ms 73968 KB Output is correct
15 Correct 142 ms 71972 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 71700 KB Output is correct
2 Correct 28 ms 71628 KB Output is correct
3 Correct 181 ms 71296 KB Output is correct
4 Correct 316 ms 74264 KB Output is correct
5 Correct 363 ms 76640 KB Output is correct
6 Correct 375 ms 81964 KB Output is correct
7 Correct 248 ms 72632 KB Output is correct
8 Correct 312 ms 74264 KB Output is correct
9 Correct 139 ms 73972 KB Output is correct
10 Correct 129 ms 71972 KB Output is correct
11 Correct 133 ms 71436 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 72236 KB Output is correct
2 Correct 682 ms 84664 KB Output is correct
3 Correct 262 ms 72636 KB Output is correct
4 Correct 778 ms 92752 KB Output is correct
5 Correct 884 ms 108496 KB Output is correct
6 Correct 472 ms 77228 KB Output is correct
7 Correct 241 ms 72632 KB Output is correct
8 Correct 110 ms 71968 KB Output is correct
9 Correct 758 ms 108496 KB Output is correct
10 Correct 574 ms 80660 KB Output is correct
11 Correct 729 ms 111420 KB Output is correct
12 Correct 704 ms 92676 KB Output is correct