oj.uz

Submission #13403

# Submission time Handle Problem Language Result Execution time Memory
13403 2015-02-17T13:43:11 Z gs14004 물병 (JOI14_bottle) C++14
70 / 100
 5000 ms 369024 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;
}

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

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);
        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 71896 KB Output is correct
2 Correct 9 ms 71900 KB Output is correct
3 Correct 4 ms 72476 KB Output is correct
4 Correct 130 ms 72480 KB Output is correct
5 Correct 129 ms 72480 KB Output is correct
6 Correct 124 ms 72476 KB Output is correct
7 Correct 128 ms 72472 KB Output is correct
8 Correct 120 ms 73644 KB Output is correct
9 Correct 114 ms 72464 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 75996 KB Output is correct
2 Correct 79 ms 80920 KB Output is correct
3 Correct 547 ms 145544 KB Output is correct
4 Correct 850 ms 220240 KB Output is correct
5 Correct 1097 ms 220816 KB Output is correct
6 Correct 518 ms 145540 KB Output is correct
7 Correct 863 ms 220240 KB Output is correct
8 Correct 1066 ms 220804 KB Output is correct
9 Correct 1617 ms 369016 KB Output is correct
10 Correct 748 ms 219212 KB Output is correct
11 Correct 826 ms 219700 KB Output is correct
12 Correct 420 ms 145812 KB Output is correct
13 Correct 415 ms 145216 KB Output is correct
14 Correct 414 ms 145812 KB Output is correct
15 Correct 405 ms 145220 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 76000 KB Output is correct
2 Correct 75 ms 80608 KB Output is correct
3 Correct 462 ms 145072 KB Output is correct
4 Correct 866 ms 220236 KB Output is correct
5 Correct 1157 ms 220816 KB Output is correct
6 Correct 1628 ms 369024 KB Output is correct
7 Correct 766 ms 219212 KB Output is correct
8 Correct 852 ms 220236 KB Output is correct
9 Correct 416 ms 145816 KB Output is correct
10 Correct 445 ms 145220 KB Output is correct
11 Correct 341 ms 108340 KB Output is correct

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1664 ms 145876 KB Output is correct
2 Execution timed out 5000 ms 152388 KB Program timed out
3 Halted 0 ms 0 KB -