Submission #140682

#TimeUsernameProblemLanguageResultExecution timeMemory
140682khrbuddy03문명 (KOI17_civilization)C++14
54 / 100
1034 ms54712 KiB
#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 state { int dist, y, x; }; 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<state> q; for (int i = 0; i < m; i++) { int x, y; cin >> x >> y; cul.siz[--y * n + --x] = 1; q.push({0, y, x}); vis[y][x] = y * n + x; } while (!q.empty()) { state s = q.front(); int dist = s.dist; int y = s.y, x = s.x; 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({dist + 1, ny, nx}); vis[ny][nx] = here; } } if (cul.siz[cul.find(here)] == m) { cout << dist << '\n'; break; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...