Submission #121373

# Submission time Handle Problem Language Result Execution time Memory
121373 2019-06-26T13:05:13 Z impri None (KOI17_civilization) C++14
Compilation error
0 ms 0 KB
#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++;
 
	}
 
}

Compilation message

civilization.cpp: In function 'void uni(int, int)':
civilization.cpp:21:6: error: reference to 'rank' is ambiguous
   if(rank[find(a)]<rank[find(b)])
      ^~~~
civilization.cpp:7:5: note: candidates are: int rank [4000001]
 int rank[4000001];
     ^~~~
In file included from /usr/include/c++/7/bits/move.h:54:0,
                 from /usr/include/c++/7/bits/nested_exception.h:40,
                 from /usr/include/c++/7/exception:143,
                 from /usr/include/c++/7/ios:39,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from civilization.cpp:1:
/usr/include/c++/7/type_traits:1468:12: note:                 template<class> struct std::rank
     struct rank
            ^~~~
civilization.cpp:21:20: error: reference to 'rank' is ambiguous
   if(rank[find(a)]<rank[find(b)])
                    ^~~~
civilization.cpp:7:5: note: candidates are: int rank [4000001]
 int rank[4000001];
     ^~~~
In file included from /usr/include/c++/7/bits/move.h:54:0,
                 from /usr/include/c++/7/bits/nested_exception.h:40,
                 from /usr/include/c++/7/exception:143,
                 from /usr/include/c++/7/ios:39,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from civilization.cpp:1:
/usr/include/c++/7/type_traits:1468:12: note:                 template<class> struct std::rank
     struct rank
            ^~~~
civilization.cpp:28:8: error: reference to 'rank' is ambiguous
     if(rank[find(a)]==rank[find(b)])
        ^~~~
civilization.cpp:7:5: note: candidates are: int rank [4000001]
 int rank[4000001];
     ^~~~
In file included from /usr/include/c++/7/bits/move.h:54:0,
                 from /usr/include/c++/7/bits/nested_exception.h:40,
                 from /usr/include/c++/7/exception:143,
                 from /usr/include/c++/7/ios:39,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from civilization.cpp:1:
/usr/include/c++/7/type_traits:1468:12: note:                 template<class> struct std::rank
     struct rank
            ^~~~
civilization.cpp:28:23: error: reference to 'rank' is ambiguous
     if(rank[find(a)]==rank[find(b)])
                       ^~~~
civilization.cpp:7:5: note: candidates are: int rank [4000001]
 int rank[4000001];
     ^~~~
In file included from /usr/include/c++/7/bits/move.h:54:0,
                 from /usr/include/c++/7/bits/nested_exception.h:40,
                 from /usr/include/c++/7/exception:143,
                 from /usr/include/c++/7/ios:39,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from civilization.cpp:1:
/usr/include/c++/7/type_traits:1468:12: note:                 template<class> struct std::rank
     struct rank
            ^~~~
civilization.cpp:29:8: error: reference to 'rank' is ambiguous
        rank[find(a)]++;
        ^~~~
civilization.cpp:7:5: note: candidates are: int rank [4000001]
 int rank[4000001];
     ^~~~
In file included from /usr/include/c++/7/bits/move.h:54:0,
                 from /usr/include/c++/7/bits/nested_exception.h:40,
                 from /usr/include/c++/7/exception:143,
                 from /usr/include/c++/7/ios:39,
                 from /usr/include/c++/7/ostream:38,
                 from /usr/include/c++/7/iostream:39,
                 from civilization.cpp:1:
/usr/include/c++/7/type_traits:1468:12: note:                 template<class> struct std::rank
     struct rank
            ^~~~
civilization.cpp: In function 'int main()':
civilization.cpp:66:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<q.size();j++) {
               ~^~~~~~~~~