Submission #55565

#	Time	Username	Problem	Language	Result	Execution time	Memory
55565		dennisstar	문명 (KOI17_civilization)	C++11	100 / 100	981 ms	55116 KiB

civilization

#include <bits/stdc++.h>
int N, K;
int stk[4000010][2];
int chk[2010][2010];
int xx[]={0,0,1,-1}, yy[]={1,-1,0,0};
struct Union_Find
{
	std::vector<int> parent, rank;
	Union_Find() { for(int i=0; i<100010; i++) parent.push_back(i), rank.push_back(1);}
	int find(int u) { return u==parent[u]?u:parent[u]=find(parent[u]);}
	int merge(int u, int v) {
		u=find(u), v=find(v);
		if(u==v)return 0;
		if(rank[u]>rank[v]) std::swap(u,v);
		parent[u]=v;
		if(rank[u]==rank[v]) ++rank[v];
		return 1;
	}
};
int check(int x, int y)
{
	if (!x||!y||x>N||y>N) return 1;
	return 0;
}
int main()
{
	scanf("%d %d", &N, &K);
	Union_Find civilization;
	int i, j, x, y;
	int top=0;
	for (i=0; i<K; i++) {
		scanf("%d %d", &x, &y);
		chk[x][y]=i+1;
		stk[top][0]=x, stk[top++][1]=y;
	}
	int fr, re;
	fr=0, re=top;
	int cnt=K, k=0, l;
	for(i=0; i<re; i++) {
		for (j=0; j<4; j++) {
			if (check(stk[i][0]+xx[j],stk[i][1]+yy[j])) continue;
			if (chk[stk[i][0]+xx[j]][stk[i][1]+yy[j]]) cnt-=civilization.merge(chk[stk[i][0]+xx[j]][stk[i][1]+yy[j]],chk[stk[i][0]][stk[i][1]]);
		}
	}
	if (cnt==1) {printf("0"); return 0;}
	while(fr<re) {
		k++;
		for (i=fr; i<re; i++) {
			for (j=0; j<4; j++) {
				if (check(stk[i][0]+xx[j],stk[i][1]+yy[j])) continue;
				if (chk[stk[i][0]+xx[j]][stk[i][1]+yy[j]]) {
					cnt-=civilization.merge(chk[stk[i][0]][stk[i][1]], chk[stk[i][0]+xx[j]][stk[i][1]+yy[j]]);
				}
				else {
					chk[stk[i][0]+xx[j]][stk[i][1]+yy[j]]=chk[stk[i][0]][stk[i][1]];
					stk[top][0]=stk[i][0]+xx[j], stk[top][1]=stk[i][1]+yy[j];
					for (l=0; l<4; l++) {
						if (check(stk[top][0]+xx[l],stk[top][1]+yy[l])) continue;
						if (chk[stk[top][0]+xx[l]][stk[top][1]+yy[l]]) {
							cnt-=civilization.merge(chk[stk[top][0]][stk[top][1]], chk[stk[top][0]+xx[l]][stk[top][1]+yy[l]]);
						}
					}
					top++;
				}
			}
		}
		if (cnt==1) {
			printf("%d", k);
			return 0;
		}
		fr=re; re=top;
	}
	return 0;
}

Compilation message (stderr)

civilization.cpp: In function 'int main()':
civilization.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~~
civilization.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 35 / 35
• Subtask 3: 46 / 46