### Andrew Stankevich’s Contest #11解题报告 » ZOJ3366

ZOJ3366.cpp

```#include <map>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int dx[] = {-1, -1, 0, 0, 1, 1};
const int dy[] = {-1, 0, -1, 1, -1, 0};
const int dz[] = {0, 1, -1, 1, 0, 1};

struct Islands {
const int s;
map<PII, int> mp;
vector<int> p, c;

Islands(int s) : s(s) {
}

int tryfind(const PII& xy) {
return mp.count(xy) == 0 ? -1 : mp[xy];
}

int find(const PII& xy) {
if (mp.count(xy) == 0) {
int z = mp.size();
p.push_back(z);
c.push_back(1);
return mp[xy] = z;
} else {
return mp[xy];
}
}

int root(int i) {
return i == p[i] ? i : p[i] = root(p[i]);
}

if (tryfind(xy) != -1) {
return;
}

int t = 1;
vector<int> v;
for (int i = 0; i < 6; ++i) {
int z = tryfind(make_pair(xy.first + dx[i], xy.second + (xy.first % 2 == 0 ? dy[i] : dz[i])));
if (z != -1) {
z = root(z);
if (std::find(v.begin(), v.end(), z) == v.end()) {
v.push_back(z);
t += c[z];
}
}
}
// printf("=> %d\n", t);

if (t > s) {
return;
}

int n = find(xy);
for (int i = 0; i < 6; ++i) {
int z = tryfind(make_pair(xy.first + dx[i], xy.second + (xy.first % 2 == 0 ? dy[i] : dz[i])));
if (z != -1) {
z = root(z);
if (z != n) {
p[z] = n;
c[n] += c[z];
}
}
}
}
};

int main() {
int n, s, x, y;

while (scanf("%d%d", &n, &s) != EOF) {
Islands islands(s);
for (int i = 0; i < n; ++i) {
scanf("%d%d", &x, &y);
}

vector<int> ans;
for (int i = 0; i < (int)islands.p.size(); ++i) {
if (islands.p[i] == i) {
ans.push_back(islands.c[i]);
}
}

sort(ans.begin(), ans.end());
printf("%d\n", (int)ans.size());
for (int i = 0; i < (int)ans.size(); ++i) {
printf("%d%c", ans[i], i == (int)ans.size() - 1 ? '\n' : ' ');
}
}

return 0;
}

// TL = 5s
// Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
// 511 	2010-07-08 14:12:42 	Accepted 	asc11e 	C++ 	3480 	2752 	anotherpeg 	Source

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//175 	2010-07-08 14:39:11 	Accepted 	asc11e 	C++ 	2750 	2748 	watashi@Zodiac 	Source
```
4 Responses to “ZOJ3366”
1. 卡卡 says:

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3908
我用index[1005][1005]记录坐标为（x，y）的点的标号，Coordinates do not exceed 500 by their absolute values，如果一个点是（x，y），那么index[x+500][y+500]记录该点的标号，为什么会错？而用map<pair,int>记录点的标号就对了。是不是这题的测试数据有问题啊

• 卡卡 says:

map<pair,int>

• watashi says:

数据是否合法你可以自己简单的assert看看？

2. 卡卡 says:

这道题的测试数据能发一份吗，我用随机数产生测试数据，再和你的程序运行的结果作对比，但是都没发现错误。诶。。

3.