Submission #132754

#	Time	Username	Problem	Language	Result	Execution time	Memory
132754		abra_stone	문명 (KOI17_civilization)	C++14	100 / 100	983 ms	34040 KiB

civilization

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define N 2005
#define K 100005
using namespace std;

int n, k, ans, ca[K], g[N][N];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
bool v[N][N];
queue<int> qx, qy, qg, qc;

int uni(int p) {
	if (ca[p] == p) return p;
	return ca[p] = uni(ca[p]);
}

void f(int x, int y, int fg, int fc) {
	if (g[x][y] == -1) return;
	if (v[x][y] == 0) {
		qx.push(x);
		qy.push(y);
		qg.push(fg);
		qc.push(fc + 1);
		v[x][y] = 1;
		return;
	}
}

int main()
{
	int i, j, t1, t2, fx, fy, fg, fc;
	cin >> n >> k;
	if (k == 1) {cout << '0' << endl; return 0;}
	for (i = 1; i <= k; i++) ca[i] = i;
	for (i = 0; i <= n + 1; i++) for (j = 0; j <= n + 1; j++) g[i][j] = -1;
	for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) g[i][j] = 0;
	for (i = 1; i <= k; i++) {
		scanf("%d %d", &fx, &fy);
		qx.push(fx);
		qy.push(fy);
		qg.push(i);
		qc.push(0);
		g[fx][fy] = i;
	}
	while (!qx.empty()) {
		fx = qx.front(), qx.pop();
		fy = qy.front(), qy.pop();
		fg = qg.front(), qg.pop();
		fc = qc.front(), qc.pop();
		g[fx][fy] = fg;
		for (i = 0; i < 4; i++) {
			if (g[fx + dx[i]][fy + dy[i]] > 0) {
				t1 = uni(g[fx + dx[i]][fy + dy[i]]);
				t2 = uni(fg);
				if (t1 != t2) {
					ca[t2] = t1;
					ans = fc;
				}
			}
		}
		for (i = 0; i < 4; i++) {
			f(fx + dx[i], fy + dy[i], fg, fc);
		}
	}
	cout << ans << endl;
    return 0;
}

Compilation message (stderr)

civilization.cpp: In function 'int main()':
civilization.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &fx, &fy);
   ~~~~~^~~~~~~~~~~~~~~~~~~

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