oj.uz

Submission #156089

# Submission time Handle Problem Language Result Execution time Memory
156089 2019-10-03T08:45:37 Z EntityIT 물병 (JOI14_bottle) C++14
100 / 100
 3243 ms 260352 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 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 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:45: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:46: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:47: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:49: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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 43636 KB Output is correct
2 Correct 53 ms 44416 KB Output is correct
3 Correct 56 ms 44784 KB Output is correct
4 Correct 149 ms 47336 KB Output is correct
5 Correct 153 ms 47368 KB Output is correct
6 Correct 150 ms 47072 KB Output is correct
7 Correct 142 ms 47280 KB Output is correct
8 Correct 162 ms 47732 KB Output is correct
9 Correct 151 ms 47564 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 58644 KB Output is correct
2 Correct 160 ms 51460 KB Output is correct
3 Correct 815 ms 111216 KB Output is correct
4 Correct 1285 ms 160792 KB Output is correct
5 Correct 1646 ms 161116 KB Output is correct
6 Correct 830 ms 111140 KB Output is correct
7 Correct 1287 ms 160916 KB Output is correct
8 Correct 1667 ms 161300 KB Output is correct
9 Correct 2487 ms 260124 KB Output is correct
10 Correct 1086 ms 160332 KB Output is correct
11 Correct 1171 ms 160532 KB Output is correct
12 Correct 533 ms 106072 KB Output is correct
13 Correct 675 ms 107372 KB Output is correct
14 Correct 513 ms 106204 KB Output is correct
15 Correct 660 ms 106680 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 58612 KB Output is correct
2 Correct 141 ms 50712 KB Output is correct
3 Correct 648 ms 111160 KB Output is correct
4 Correct 1299 ms 160912 KB Output is correct
5 Correct 1707 ms 161416 KB Output is correct
6 Correct 2498 ms 260352 KB Output is correct
7 Correct 1157 ms 160548 KB Output is correct
8 Correct 1252 ms 161324 KB Output is correct
9 Correct 552 ms 106580 KB Output is correct
10 Correct 682 ms 107236 KB Output is correct
11 Correct 636 ms 83340 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1028 ms 114232 KB Output is correct
2 Correct 2044 ms 145984 KB Output is correct
3 Correct 1107 ms 160520 KB Output is correct
4 Correct 2714 ms 172172 KB Output is correct
5 Correct 3243 ms 195916 KB Output is correct
6 Correct 1656 ms 164664 KB Output is correct
7 Correct 1084 ms 160396 KB Output is correct
8 Correct 483 ms 105940 KB Output is correct
9 Correct 3096 ms 196256 KB Output is correct
10 Correct 1940 ms 153036 KB Output is correct
11 Correct 2985 ms 205616 KB Output is correct
12 Correct 2513 ms 183208 KB Output is correct