oj.uz

Submission #13404

# Submission time Handle Problem Language Result Execution time Memory
13404 2015-02-17T13:45:23 Z gs14004 물병 (JOI14_bottle) C++14
70 / 100
 5000 ms 369808 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[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;
        if(r[p] > r[q]) pa[p] = q;
        else pa[q] = p;
        if(r[p] == r[q]) r[q]++;
        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 72680 KB Output is correct
2 Correct 0 ms 72684 KB Output is correct
3 Correct 6 ms 73260 KB Output is correct
4 Correct 125 ms 73264 KB Output is correct
5 Correct 120 ms 73264 KB Output is correct
6 Correct 118 ms 73260 KB Output is correct
7 Correct 114 ms 73256 KB Output is correct
8 Correct 127 ms 74428 KB Output is correct
9 Correct 121 ms 73248 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 76780 KB Output is correct
2 Correct 76 ms 81704 KB Output is correct
3 Correct 533 ms 146328 KB Output is correct
4 Correct 843 ms 221024 KB Output is correct
5 Correct 1090 ms 221600 KB Output is correct
6 Correct 548 ms 146324 KB Output is correct
7 Correct 850 ms 221024 KB Output is correct
8 Correct 1081 ms 221588 KB Output is correct
9 Correct 1607 ms 369800 KB Output is correct
10 Correct 747 ms 219996 KB Output is correct
11 Correct 797 ms 220484 KB Output is correct
12 Correct 423 ms 146596 KB Output is correct
13 Correct 431 ms 146000 KB Output is correct
14 Correct 388 ms 146596 KB Output is correct
15 Correct 430 ms 146004 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 76784 KB Output is correct
2 Correct 64 ms 81392 KB Output is correct
3 Correct 457 ms 145856 KB Output is correct
4 Correct 902 ms 221020 KB Output is correct
5 Correct 1154 ms 221600 KB Output is correct
6 Correct 1618 ms 369808 KB Output is correct
7 Correct 744 ms 219996 KB Output is correct
8 Correct 862 ms 221020 KB Output is correct
9 Correct 418 ms 146600 KB Output is correct
10 Correct 468 ms 146004 KB Output is correct
11 Correct 342 ms 109124 KB Output is correct

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1695 ms 146660 KB Output is correct
2 Execution timed out 5000 ms 153172 KB Program timed out
3 Halted 0 ms 0 KB -