Submission #13399

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
13399	2015-02-17T13:20:23 Z	gs14004	물병 (JOI14_bottle)	C++14	Compilation error	0 ms	0 KB

bottle

#include <cstdio>
#include <queue>
#include <vector>
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);
        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);
                break;
            }
        }
        puts("-1");
    }
}

Compilation message

bottle.cpp: In function ‘void make_tree()’:
bottle.cpp:80:37: error: ‘sort’ was not declared in this scope
     sort(cand.begin(),cand.end(),cmp);
                                     ^
bottle.cpp:81:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<cand.size(); i++) {
                    ^
bottle.cpp: In function ‘int main()’:
bottle.cpp:99:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j=0; j<tree.size(); j++) {
                        ^
bottle.cpp: In function ‘void make_tree()’:
bottle.cpp:44:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&px,&py);
                               ^
bottle.cpp: In function ‘int main()’:
bottle.cpp:89:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d %d",&n,&m,&p,&q);
                                     ^
bottle.cpp:91:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",str[i]);
                           ^
bottle.cpp:98:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&s,&e);
                             ^