oj.uz

Submission #156096

# Submission time Handle Problem Language Result Execution time Memory
156096 2019-10-03T09:12:18 Z Flying_dragon_02 물병 (JOI14_bottle) C++14
100 / 100
 1468 ms 115392 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int mod = 1e9 + 7;

const int inf = 1e9;

int add(int x, int y) {
    return (1ll * x + 1ll * y) % mod;
}

int del(int x, int y) {
    return ((1ll * x - 1ll * y) % mod + mod) % mod;
}

int mul(int x, int y) {
    return (1ll * x * 1ll * y) % mod;
}

const int M = 2e5 + 5;
const int N = 2e3 + 5;

int h, w, p, g, d[N][N], type[N][N];
char a[N][N];

vector<ii> query[M];

queue<ii> q;

bool check(int x, int y) {
    return (1 <= x && x <= h && 1 <= y && y <= w && a[x][y] != '#');
}

int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};

vector< pair<int, ii> > edge;

int ans[M], pSet[M], sz[M];

vector<int> vec[M];

int findSet(int u) {
    if(u == pSet[u]) return u;
    else return pSet[u] = findSet(pSet[u]);
}

void unionSet(int lmao, int u, int v) {
    //cout << lmao << " " << u << " " << v << "\n";
    u = findSet(u), v = findSet(v);
    if(u == v) return ;
    if(sz[u] > sz[v]) swap(u, v);
    for(int i = 0; i < vec[u].size(); i++) {
        int id = vec[u][i];
        for(int j = 0; j < query[id].size(); j++) {
            ii w = query[id][j];
            //cout << id << " " << w.fi << " " << w.se << " " << findSet(w.se) << "\n";
            if(findSet(w.se) == v)
                ans[w.fi] = lmao;
        }
        vec[v].pb(id);
    }
    vec[u].clear();
    sz[v] += sz[u];
    pSet[u] = v;
}

int main() {
    cin.tie(0), ios_base::sync_with_stdio(0);
    cin >> h >> w >> p >> g;
    for(int i = 1; i <= h; i++) {
        for(int j = 1; j <= w; j++)
            d[i][j] = inf;
    }
    for(int i = 1; i <= p; i++) {
        pSet[i] = i, sz[i] = 1;
        vec[i].pb(i);
    }
    for(int i = 1; i <= h; i++) {
        for(int j = 1; j <= w; j++)
            cin >> a[i][j];
    }
    for(int i = 1; i <= p; i++) {
        int u, v;
        cin >> u >> v;
        d[u][v] = 0;
        type[u][v] = i;
        q.push({u, v});
    }
    for(int i = 1; i <= g; i++) {
        int u, v;
        cin >> u >> v;
        query[u].pb({i, v});
        query[v].pb({i, u});
    }
    while(!q.empty()) {
        ii x = q.front();
        q.pop();
        for(int i = 0; i < 4; i++) {
            ii y = mp(x.fi + dx[i], x.se + dy[i]);
            if(!check(y.fi, y.se)) continue;
            if(d[y.fi][y.se] == inf) {
                d[y.fi][y.se] = d[x.fi][x.se] + 1;
                type[y.fi][y.se] = type[x.fi][x.se];
                q.push(y);
            }
            else if(type[x.fi][x.se] != type[y.fi][y.se])
                edge.pb({d[y.fi][y.se] + d[x.fi][x.se], {type[x.fi][x.se], type[y.fi][y.se]}});
        }
    }
    sort(edge.begin(), edge.end());
    for(int i = 1; i <= g; i++)
        ans[i] = -1;
    for(int i = 0; i < edge.size(); i++)
        unionSet(edge[i].fi, edge[i].se.fi, edge[i].se.se);
    for(int i = 1; i <= g; i++)
        cout << ans[i] << "\n";
}

Compilation message

bottle.cpp: In function 'void unionSet(int, int, int)':
bottle.cpp:61:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < vec[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~
bottle.cpp:63:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < query[id].size(); j++) {
                        ~~^~~~~~~~~~~~~~~~~~
bottle.cpp: In function 'int main()':
bottle.cpp:122:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < edge.size(); i++)
                    ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 10616 KB Output is correct
2 Correct 14 ms 12152 KB Output is correct
3 Correct 15 ms 12280 KB Output is correct
4 Correct 88 ms 17400 KB Output is correct
5 Correct 84 ms 17524 KB Output is correct
6 Correct 88 ms 17400 KB Output is correct
7 Correct 82 ms 17400 KB Output is correct
8 Correct 86 ms 17744 KB Output is correct
9 Correct 84 ms 17572 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 31808 KB Output is correct
2 Correct 47 ms 15368 KB Output is correct
3 Correct 294 ms 46516 KB Output is correct
4 Correct 435 ms 48936 KB Output is correct
5 Correct 480 ms 52516 KB Output is correct
6 Correct 293 ms 46532 KB Output is correct
7 Correct 424 ms 49268 KB Output is correct
8 Correct 484 ms 52516 KB Output is correct
9 Correct 509 ms 59136 KB Output is correct
10 Correct 325 ms 47056 KB Output is correct
11 Correct 399 ms 48980 KB Output is correct
12 Correct 187 ms 44844 KB Output is correct
13 Correct 226 ms 42756 KB Output is correct
14 Correct 180 ms 44832 KB Output is correct
15 Correct 220 ms 42488 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 31884 KB Output is correct
2 Correct 41 ms 14040 KB Output is correct
3 Correct 264 ms 45704 KB Output is correct
4 Correct 418 ms 49192 KB Output is correct
5 Correct 460 ms 52800 KB Output is correct
6 Correct 520 ms 59460 KB Output is correct
7 Correct 320 ms 47332 KB Output is correct
8 Correct 440 ms 49448 KB Output is correct
9 Correct 198 ms 45340 KB Output is correct
10 Correct 231 ms 42884 KB Output is correct
11 Correct 219 ms 42096 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 53600 KB Output is correct
2 Correct 1035 ms 76040 KB Output is correct
3 Correct 343 ms 47016 KB Output is correct
4 Correct 1256 ms 89488 KB Output is correct
5 Correct 1468 ms 115392 KB Output is correct
6 Correct 604 ms 59028 KB Output is correct
7 Correct 322 ms 47152 KB Output is correct
8 Correct 155 ms 42924 KB Output is correct
9 Correct 1366 ms 107488 KB Output is correct
10 Correct 1031 ms 71004 KB Output is correct
11 Correct 1270 ms 112748 KB Output is correct
12 Correct 1076 ms 85960 KB Output is correct