oj.uz

Submission #14630

# Submission time Handle Problem Language Result Execution time Memory
14630 2015-05-23T07:54:36 Z gs14004 물병 (JOI14_bottle) C++14
100 / 100
 908 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 domain[2005][2005], depth[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};

void process(int x){
    for (int i=1; (1<<i) <= dep[x]; i++) {
        pa[x][i] = pa[pa[x][i-1]][i-1];
        val[x][i] = max(val[x][i-1],val[pa[x][i-1]][i-1]);
    }
}

void dfs(int x, int p, int e, int d){
    pa[x][0] = p;
    val[x][0] = e;
    dep[x] = d;
    process(x);
    for (int i=0; i<graph[x].size(); i++) {
        if(graph[x][i].second == p) continue;
        dfs(graph[x][i].second,x,graph[x][i].first,d+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);
        domain[px][py] = i;
        depth[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(domain[xf+dx[i]][yf+dy[i]]) continue;
            domain[xf+dx[i]][yf+dy[i]] = domain[xf][yf];
            depth[xf+dx[i]][yf+dy[i]] = depth[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 && domain[i][j] != domain[i][j+1] && domain[i][j] && domain[i][j+1]){
                cand.push_back({domain[i][j],domain[i][j+1],depth[i][j] + depth[i][j+1]});
            }
            if(i + 1 != n && domain[i][j] != domain[i+1][j] && domain[i][j] && domain[i+1][j]){
                cand.push_back({domain[i][j],domain[i+1][j],depth[i][j] + depth[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));
        }
    }
}

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();
    dfs(1,0,0,0);
    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 4 ms 71296 KB Output is correct
2 Correct 5 ms 71296 KB Output is correct
3 Correct 0 ms 71296 KB Output is correct
4 Correct 92 ms 71296 KB Output is correct
5 Correct 105 ms 71296 KB Output is correct
6 Correct 92 ms 71296 KB Output is correct
7 Correct 104 ms 71296 KB Output is correct
8 Correct 100 ms 71500 KB Output is correct
9 Correct 100 ms 71296 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 71700 KB Output is correct
2 Correct 30 ms 72636 KB Output is correct
3 Correct 242 ms 72060 KB Output is correct
4 Correct 312 ms 74336 KB Output is correct
5 Correct 338 ms 76640 KB Output is correct
6 Correct 231 ms 72060 KB Output is correct
7 Correct 340 ms 74264 KB Output is correct
8 Correct 346 ms 76644 KB Output is correct
9 Correct 349 ms 81956 KB Output is correct
10 Correct 252 ms 72632 KB Output is correct
11 Correct 275 ms 73964 KB Output is correct
12 Correct 121 ms 73968 KB Output is correct
13 Correct 141 ms 71972 KB Output is correct
14 Correct 97 ms 73968 KB Output is correct
15 Correct 121 ms 71972 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 71700 KB Output is correct
2 Correct 26 ms 71628 KB Output is correct
3 Correct 202 ms 71296 KB Output is correct
4 Correct 330 ms 74264 KB Output is correct
5 Correct 362 ms 76640 KB Output is correct
6 Correct 356 ms 81964 KB Output is correct
7 Correct 244 ms 72632 KB Output is correct
8 Correct 323 ms 74264 KB Output is correct
9 Correct 127 ms 73972 KB Output is correct
10 Correct 123 ms 71972 KB Output is correct
11 Correct 126 ms 71480 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 72236 KB Output is correct
2 Correct 654 ms 84688 KB Output is correct
3 Correct 258 ms 72636 KB Output is correct
4 Correct 800 ms 92752 KB Output is correct
5 Correct 908 ms 108496 KB Output is correct
6 Correct 493 ms 77228 KB Output is correct
7 Correct 238 ms 72632 KB Output is correct
8 Correct 101 ms 71968 KB Output is correct
9 Correct 765 ms 108496 KB Output is correct
10 Correct 610 ms 89912 KB Output is correct
11 Correct 797 ms 111420 KB Output is correct
12 Correct 733 ms 97988 KB Output is correct