oj.uz

Submission #13401

# Submission time Handle Problem Language Result Execution time Memory
13401 2015-02-17T13:21:23 Z gs14004 물병 (JOI14_bottle) C++14
70 / 100
 5000 ms 335432 KB 
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

struct edg{int s,e,x;};
vector<edg> tree;

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];

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 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)){
            tree.push_back(cand[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();
    for (int i=0; i<q; i++) {
        disj.init(p);
        int s,e;
        scanf("%d %d",&s,&e);
        int nf = 1;
        for (int j=0; j<tree.size(); j++) {
            disj.uni(tree[j].s,tree[j].e);
            if(disj.find(s) == disj.find(e)){
                printf("%d\n",tree[j].x);
                nf = 0;
                break;
            }
        }
        if(nf)puts("-1");
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 38304 KB Output is correct
2 Correct 8 ms 38308 KB Output is correct
3 Correct 12 ms 38884 KB Output is correct
4 Correct 579 ms 38888 KB Output is correct
5 Correct 570 ms 38888 KB Output is correct
6 Correct 571 ms 38884 KB Output is correct
7 Correct 558 ms 38880 KB Output is correct
8 Correct 599 ms 40052 KB Output is correct
9 Correct 550 ms 38872 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 42404 KB Output is correct
2 Correct 72 ms 47328 KB Output is correct
3 Correct 532 ms 111952 KB Output is correct
4 Correct 835 ms 186648 KB Output is correct
5 Correct 1056 ms 187224 KB Output is correct
6 Correct 534 ms 111948 KB Output is correct
7 Correct 857 ms 186648 KB Output is correct
8 Correct 1060 ms 187212 KB Output is correct
9 Correct 1586 ms 335424 KB Output is correct
10 Correct 720 ms 185620 KB Output is correct
11 Correct 818 ms 186108 KB Output is correct
12 Correct 377 ms 112220 KB Output is correct
13 Correct 406 ms 111624 KB Output is correct
14 Correct 391 ms 112220 KB Output is correct
15 Correct 424 ms 111628 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 42408 KB Output is correct
2 Correct 76 ms 47016 KB Output is correct
3 Correct 482 ms 111480 KB Output is correct
4 Correct 1930 ms 186644 KB Output is correct
5 Correct 2184 ms 187224 KB Output is correct
6 Correct 2673 ms 335432 KB Output is correct
7 Correct 776 ms 185620 KB Output is correct
8 Correct 1878 ms 186644 KB Output is correct
9 Correct 1558 ms 112224 KB Output is correct
10 Correct 1382 ms 111628 KB Output is correct
11 Correct 1257 ms 74748 KB Output is correct

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5000 ms 112284 KB Program timed out
2 Halted 0 ms 0 KB -