Submission #140683

#	Time	Username	Problem	Language	Result	Execution time	Memory
140683		khrbuddy03	문명 (KOI17_civilization)	C++14	54 / 100	1058 ms	54092 KiB

civilization

#include <bits/stdc++.h>

using namespace std;

const int inf = 2e3 + 9;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

struct ds {
    int par[inf * inf], siz[inf * inf];
    inline int find(int u) {
        if (u == par[u]) return u;
        return par[u] = find(par[u]);
    }
    inline void merge(int u, int v) {
        u = find(u); v = find(v);
        if (u == v) return;
        par[u] = v;
        siz[v] += siz[u];
        siz[u] = 0;
    }
} cul;

int n, m;
int vis[inf][inf];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n * n; ++i) cul.par[i] = i;
    memset(vis, -1, sizeof(vis));
    queue<pair<int, pair<int, int>>> q;
    for (int i = 0; i < m; i++) {
        int x, y; cin >> x >> y;
        cul.siz[--y * n + --x] = 1;
        q.push(make_pair(0, make_pair(y, x)));
        vis[y][x] = y * n + x;
    }
    while (!q.empty()) {
        int dist = q.front().first;
        int y = q.front().second.first, x = q.front().second.second;
        int here = y * n + x;
        q.pop();
        cul.merge(here, vis[y][x]);
        for (int i = 0; i < 4; ++i) {
            int ny = y + dy[i], nx = x + dx[i];
            if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
            int there = ny * n + nx;
            if (cul.siz[cul.find(there)] && cul.siz[cul.find(here)]) cul.merge(there, here);
            if (vis[ny][nx] == -1) {
                q.push(make_pair(dist + 1, make_pair(ny, nx)));
                vis[ny][nx] = here;
            }
        }
        if (cul.siz[cul.find(here)] == m) {
            cout << dist << '\n';
            break;
        }
    }
}

• Subtask 1: 19 / 19
• Subtask 2: 35 / 35
• Subtask 3: 0 / 46