| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 121432 |
2019-06-26T14:06:02 Z |
impri |
None (KOI17_civilization) |
C++14 |
|
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;
^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1064 ms |
2048 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1064 ms |
2048 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1064 ms |
2048 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
