## Submission #121432

# Submission time Handle Problem Language Result Execution time Memory
121432 2019-06-26T14:06:02 Z impri None (KOI17_civilization) C++14
0 / 100
1000 ms 2048 KB
```#include<iostream>
#include<queue>
using namespace std;

int parent[4000001];
int siz[4000001];
int rank2[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;
a=find(a);
b=find(b);
if(rank2[a]<rank2[b])
{	siz[b] += siz[a];
parent[a] = b;
}
else{
siz[a] += siz[b];
parent[b] = a;
if(rank2[a]==rank2[b])
rank2[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) {
ios_base::sync_with_stdio(false);cin.tie(0);
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 < 2; 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++;

}

}```

### Compilation message

```civilization.cpp: In function 'int main()':
civilization.cpp:69:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<q.size();j++) {
~^~~~~~~~~
civilization.cpp:16:20: warning: 'point' may be used uninitialized in this function [-Wmaybe-uninitialized]
return parent[n] = find(parent[n]);
~~~~~~~~~~^~~~~~~~~~~~~~~~~
civilization.cpp:50:6: note: 'point' was declared here
int point;
^~~~~```

#### Subtask #1 0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 2048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

#### Subtask #2 0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 2048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

#### Subtask #3 0 / 46.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 2048 KB Time limit exceeded
2 Halted 0 ms 0 KB -