| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 121373 | impri | 문명 (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<iostream>
#include<queue>
using namespace std;
int parent[4000001];
int siz[4000001];
int rank[4000001];
int mov[4][2] = { 1,0,
0,1,
0,-1,
-1,0 };
int find(int n) {
if (parent[n] == n)
return n;
else
return parent[n] = find(parent[n]);
}
void uni(int a, int b) {
if (find(a) == find(b))
return;
if(rank[find(a)]<rank[find(b)])
{ siz[find(b)] += siz[find(a)];
parent[find(a)] = find(b);
}
else{
siz[find(a)] += siz[find(b)];
parent[find(b)] = find(a);
if(rank[find(a)]==rank[find(b)])
rank[find(a)]++;
}
}
int mapping(int a, int b) {
return a * 2000 + b;
}
int val(int a, int b, int c) {
if (a < c && b >= 0 && a >= 0 && b < c)
return 1;
return 0;
}
int area[2000][2000];
int main(void) {
int n, k;
cin >> n >> k;
int civnumber = k;
deque<pair<int, int> >q;
int point;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
parent[mapping(i, j)] = mapping(i, j);
siz[mapping(i, j)] = 1;
}
}
for (int i = 0; i < k; i++) {
int a, b;
cin >> a >> b;
point = mapping(a - 1, b - 1);
q.push_back({ a-1,b-1 });
area[a - 1][b - 1] = 1;
}
int year = 0;
while (1) {
for(int j=0;j<q.size();j++) {
int a = q[j].first;
int b = q[j].second;
for (int i = 0; i < 4; i++) {
int nexta = a + mov[i][0];
int nextb = b + mov[i][1];
if (val(nexta, nextb, n) && area[nexta][nextb] ) {
uni(mapping(nexta,nextb),mapping(a,b));
}
}
}
if (siz[find(point)] == civnumber) {
cout << year;
return 0;
}
int siz2 = q.size();
for (int i = 0; i < siz2; i++) {
int a = q.front().first;
int b = q.front().second;
q.pop_front();
for (int j = 0; j < 4; j++) {
int nexta = a + mov[j][0];
int nextb = b + mov[j][1];
if (val(nexta, nextb, n) && area[nexta][nextb] == 0) {
q.push_back({ nexta,nextb });
civnumber++;
area[nexta][nextb] = 1;
}
}
}
year++;
}
}