Submission #55563

#	Time	Username	Problem	Language	Result	Execution time	Memory
55563		dennisstar	문명 (KOI17_civilization)	C++11	0 / 100	5 ms	2048 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;
	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])&&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: 0 / 19
• Subtask 2: 0 / 35
• Subtask 3: 0 / 46