| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 85982 | tjdgus4384 | 문명 (KOI17_civilization) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<cstdio>
#include<string.h>
#include<queue>
using namespace std;
queue<pair<pair<int, int>, pair<int, int> > > q;
int pa[100001], sz[100001], rank[100001], ar[2001][2001];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int find(int u)
{
if(pa[u] == u) return u;
return pa[u] = find(pa[u]);
}
void merge(int u, int v)
{
u = find(u); v = find(v);
if(u == v) return;
if(rank[u] > rank[v]) swap(u, v);
pa[u] = v;
sz[v] += sz[u];
if(rank[u] == rank[v]) rank[v]++;
}
int main()
{
int n, k;
scanf("%d %d", &n, &k);
for(int i = 1;i <= k;i++)
{
int x, y;
scanf("%d %d", &x, &y);
q.push({{x, y}, {i, 0}});
pa[i] = i;
sz[i] = 1;
}
while(!q.empty())
{
int x = q.front().first.first;
int y = q.front().first.second;
int s = q.front().second.first;
int t = q.front().second.second;
q.pop();
if(ar[x][y] == 0)
{
ar[x][y] = s;
for(int i = 0;i < 4;i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if(nx < 1 || nx > n || ny < 1 || ny > n) continue;
if(ar[nx][ny] == 0) q.push({{nx, ny}, {s, t + 1}});
else merge(ar[nx][ny], s);
}
}
else
{
merge(ar[x][y], s);
}
if(sz[find(1)] == k)
{
printf("%d", t);
return 0;
}
}
}