Submission #156096

#	Time	Username	Problem	Language	Result	Execution time	Memory
156096		Flying_dragon_02	물병 (JOI14_bottle)	C++14	100 / 100	1468 ms	115392 KiB

bottle

#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 (stderr)

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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30