oj.uz

Submission #156086

# Submission time Handle Problem Language Result Execution time Memory
156086 2019-10-03T08:27:23 Z EntityIT 물병 (JOI14_bottle) C++14
30 / 100
 672 ms 68664 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 44792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 57212 KB Output is correct
2 Correct 86 ms 47096 KB Output is correct
3 Correct 354 ms 64572 KB Output is correct
4 Correct 507 ms 64776 KB Output is correct
5 Correct 595 ms 65144 KB Output is correct
6 Correct 329 ms 64632 KB Output is correct
7 Correct 547 ms 64904 KB Output is correct
8 Correct 615 ms 65244 KB Output is correct
9 Correct 672 ms 65592 KB Output is correct
10 Correct 364 ms 64120 KB Output is correct
11 Correct 480 ms 64616 KB Output is correct
12 Correct 174 ms 61432 KB Output is correct
13 Correct 237 ms 61688 KB Output is correct
14 Correct 164 ms 61432 KB Output is correct
15 Correct 239 ms 61652 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 57208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 599 ms 68664 KB Output isn't correct
2 Halted 0 ms 0 KB -