oj.uz

Submission #13402

# Submission time Handle Problem Language Result Execution time Memory
13402 2015-02-17T13:41:20 Z gs14004 물병 (JOI14_bottle) C++14
70 / 100
 5000 ms 369028 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], 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 dfs(int x, int p, int e, int d){
    pa[x][0] = p;
    val[x][0] = e;
    dep[x] = d;
    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]);
    }
    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;
}
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)){
            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++) {
        disj.init(p);
        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 71900 KB Output is correct
2 Correct 6 ms 71904 KB Output is correct
3 Correct 9 ms 72480 KB Output is correct
4 Correct 121 ms 72484 KB Output is correct
5 Correct 142 ms 72484 KB Output is correct
6 Correct 126 ms 72480 KB Output is correct
7 Correct 112 ms 72476 KB Output is correct
8 Correct 134 ms 73648 KB Output is correct
9 Correct 127 ms 72468 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 76000 KB Output is correct
2 Correct 78 ms 80924 KB Output is correct
3 Correct 522 ms 145548 KB Output is correct
4 Correct 826 ms 220244 KB Output is correct
5 Correct 1089 ms 220820 KB Output is correct
6 Correct 511 ms 145544 KB Output is correct
7 Correct 837 ms 220244 KB Output is correct
8 Correct 1101 ms 220808 KB Output is correct
9 Correct 1636 ms 369020 KB Output is correct
10 Correct 749 ms 219216 KB Output is correct
11 Correct 794 ms 219704 KB Output is correct
12 Correct 410 ms 145816 KB Output is correct
13 Correct 416 ms 145220 KB Output is correct
14 Correct 400 ms 145816 KB Output is correct
15 Correct 452 ms 145224 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 76004 KB Output is correct
2 Correct 71 ms 80612 KB Output is correct
3 Correct 437 ms 145076 KB Output is correct
4 Correct 877 ms 220240 KB Output is correct
5 Correct 1108 ms 220820 KB Output is correct
6 Correct 1608 ms 369028 KB Output is correct
7 Correct 739 ms 219216 KB Output is correct
8 Correct 840 ms 220240 KB Output is correct
9 Correct 426 ms 145820 KB Output is correct
10 Correct 457 ms 145224 KB Output is correct
11 Correct 322 ms 108344 KB Output is correct

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1687 ms 145880 KB Output is correct
2 Execution timed out 5000 ms 152392 KB Program timed out
3 Halted 0 ms 0 KB -