Submission #156086

#	Time	Username	Problem	Language	Result	Execution time	Memory
156086		EntityIT	물병 (JOI14_bottle)	C++14	30 / 100	672 ms	68664 KiB

bottle

#include<bits/stdc++.h>

using namespace std;

const int NR = (int)2e3 + 5, NC = NR, NBuilding = (int)2e5 + 5, NQuery = NBuilding;
int nR, nC, nBuilding, nQuery, x[NBuilding], y[NBuilding], dist[NR][NC], type[NR][NC], dx[] = { -1, 0, 1, 0 }, dy[] = { 0, 1, 0, -1 }, ans[NQuery];
char c[NR][NC];
vector< array<int, 3> > edge;
vector<int> querySet[NBuilding];

struct Query {
    int s, t;
    Query(int _s = 0, int _t = 0) : s(_s), t(_t) {}
    int oth(int _) { return s ^ t ^ _; }
} query[NQuery];

struct Dsu {
    int pSet[NBuilding], szSet[NBuilding];
    Dsu() {
        for (int i = 0; i < NBuilding; ++i) {
            pSet[i] = i;
            szSet[i] = 1;
        }
    }
    int findSet(int i) { return i == pSet[i] ? i : pSet[i] = findSet(pSet[i]); }
    bool unionSet(int i, int j) {
        i = findSet(i); j = findSet(j);
        if (i == j) return false;
        if (szSet[i] > szSet[j]) swap(i, j);
        szSet[j] += szSet[i];
        pSet[i] = j;
        return true;
    }
} dsu;

struct Dsu2 {
    int pSet[NBuilding];
    set<int> eleSet[NBuilding];
    Dsu2() {
        for (int i = 0; i < NBuilding; ++i) {
            pSet[i] = i;
            eleSet[i].insert(i);
        }
    }
    int findSet(int i) { return i == pSet[i] ? i : pSet[i] = findSet(pSet[i]); }
    void unionSet(int i, int j, int w) {
        i = findSet(i); j = findSet(j);
        if (i == j) return ;
        if (eleSet[i].size() > eleSet[j].size() ) swap(i, j);
        for (int buildingId : eleSet[i]) {
            for (int queryId : querySet[buildingId]) {
                if (eleSet[j].count(query[queryId].oth(buildingId) ) ) ans[queryId] = w;
            }
        }
        for (int buildingId : eleSet[i]) eleSet[j].insert(buildingId);
        pSet[i] = j;
    }
} dsu2;

bool valid(int _x, int _y) { return _x > 0 && _x <= nR && _y > 0 && _y <= nC && c[_x][_y] != '#'; }

int main() {
//    freopen("input", "r", stdin);
    scanf(" %d %d %d %d", &nR, &nC, &nBuilding, &nQuery);
    for (int i = 1; i <= nR; ++i) scanf(" %s", c[i] + 1);
    for (int i = 1; i <= nBuilding; ++i) scanf(" %d %d", x + i, y + i);
    for (int i = 1; i <= nQuery; ++i) {
        int s, t; scanf(" %d %d", &s, &t);
        query[i] = Query(s, t);
        querySet[s].emplace_back(i);
        querySet[t].emplace_back(i);
    }

    memset(dist, -1, sizeof dist);
    queue< pair<int, int> > q;
    for (int i = 1; i <= nBuilding; ++i) {
        dist[ x[i] ][ y[i] ] = 0;
        type[ x[i] ][ y[i] ] = i;
        q.emplace(x[i], y[i]);
    }
    while(!q.empty() ) {
        auto fron = q.front(); q.pop();
        int curX = fron.first, curY = fron.second;
        for (int dir = 0; dir < 4; ++dir) {
            int nxtX = curX + dx[dir], nxtY = curY + dy[dir];
            if (!valid(nxtX, nxtY) ) continue ;
            if (dist[nxtX][nxtY] == -1) {
                dist[nxtX][nxtY] = dist[curX][curY] + 1;
                type[nxtX][nxtY] = type[curX][curY];
                q.emplace(nxtX, nxtY);
            }
            else {
                if (dsu.unionSet(type[nxtX][nxtY], type[curX][curY]) ) edge.emplace_back(array<int, 3>{ dist[nxtX][nxtY] + dist[curX][curY], type[curX][curY], type[nxtX][nxtY] } );
            }
        }
    }

    sort(edge.begin(), edge.end() );
    memset(ans, -1, sizeof ans);
    for (auto _ : edge) dsu2.unionSet(_[1], _[2], _[0]);

    for (int i = 1; i <= nQuery; ++i) printf("%d\n", ans[i]);

    return 0;
}

Compilation message (stderr)

bottle.cpp: In function 'int main()':
bottle.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %d %d %d %d", &nR, &nC, &nBuilding, &nQuery);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:65:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= nR; ++i) scanf(" %s", c[i] + 1);
                                   ~~~~~^~~~~~~~~~~~~~~~~
bottle.cpp:66:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= nBuilding; ++i) scanf(" %d %d", x + i, y + i);
                                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bottle.cpp:68:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int s, t; scanf(" %d %d", &s, &t);
                   ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 30 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30