Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include <cstdio>
- #include <algorithm>
- #include <cstdlib>
- #include <ctime>
- #include <cstring>
- #include <map>
- #include <iostream>
- #include <algorithm>
- #include <functional>
- #include <vector>
- #define TASK "snakes"
- #ifdef WIN32
- #define LLD "%I64u"
- #else
- #define LLD "%llu"
- #endif
- #define fill(a, x) memset(a, x, sizeof(a))
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- #define maxn 3000
- #define maxh 110
- struct point {
- int x, y;
- point nil () {
- point res = {};
- return res;
- }
- };
- vector < vector < int > > res;
- int n, m, k;
- int f[maxn][2];
- int op[maxh][maxh];
- int dist[maxn];
- int go[maxn][maxn];
- const int DX[8] = {1, 1, 1, 0, -1, -1, -1, 0};
- const int DY[8] = {1, 0, -1, -1, -1, 0, 1, 1};
- int q[maxn];
- int beg, en;
- int used[maxn];
- int edge[maxn][maxn];
- int num[maxn], mv[maxn];
- int cost[maxh][maxh];
- bool inPoly(int x, int y, int id) {
- int num = 0;
- for (int kk = x + 1; kk <= m; ++kk)
- if (op[kk][y] == id) num += max(cost[kk][y], -100);
- return (num & 1);
- }
- int main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- freopen(TASK".in", "r", stdin);
- freopen(TASK".out", "w", stdout);
- #endif
- cin >> m >> n >> k;
- int numtest = 0;
- do{
- memset(op, 0, sizeof(op));
- memset(go, 0, sizeof(go));
- memset(used, 0, sizeof(used));
- memset(num, 0, sizeof(num));
- memset(mv, 0, sizeof(mv));
- memset(cost, 0, sizeof(cost));
- vector < point > curP;
- point curpo;
- for (int i = 1; i <= k; ++i) {
- int nm;
- cin >> nm;
- curP.clear ();
- for (int it = 1; it <= nm; ++it) {
- int a, b;
- cin >> a >> b;
- curpo.x = a;
- curpo.y = b;
- curP.push_back (curpo);
- op[a][b] = i;
- f[i][0] = a; f[i][1] = b;
- }
- // cout << "i = " << i << endl;
- for (int pp = 0; pp < nm; ++pp)
- curP.push_back (curP[pp]);
- for (int it = 1; it < nm + 1; ++it) {
- // cout << curP[it].x << " " << curP[it].y << endl;
- if (curP[it].x == curP[it - 1].x && curP[it].y > curP[it - 1].y ||
- curP[it].x == curP[it + 1].x && curP[it].y > curP[it + 1].y)
- cost[curP[it].x][curP[it].y] = 1;
- }
- }
- for (int i = 1; i <= m; ++i)
- for (int j = 1; j <= n; ++j) {
- for (int d = 0; d < 8; ++d) {
- if (op[i + DX[d]][j + DY[d]] != op[i][j])
- go[op[i + DX[d]][j + DY[d]]][op[i][j]] =
- go[op[i][j]][op[i + DX[d]][j + DY[d]]] = true;
- }
- }
- beg = 1; en = 0;
- q[++en] = 0;
- used[0] = true;
- dist[0] = 0;
- while(beg <= en) {
- int cur = q[beg++];
- used[cur] = true;
- for (int i = 1; i <= k; ++i)
- if (go[cur][i] && !used[i]) {
- q[++en] = i;
- used[i] = true;
- dist[i] = dist[cur] + 1;
- }
- }
- memset(used, 0, sizeof(used));
- for (int i = 1; i <= k; ++i) {
- for (int j = 1; j <= k; ++j)
- if (go[i][j] && dist[j] == dist[i] + 1 && inPoly(f[j][0], f[j][1], i)) {
- ++num[i];
- edge[i][num[i]] = j;
- ++mv[j];
- }
- }
- /* for (int j = 1; j <= n; ++j) {
- for (int i = 1; i <= m; ++i)
- cout << cost[i][j] << " ";
- cout << endl;
- }*/
- for (int i = 1; i <= k; ++i)
- if (num[i] > 1) {
- for (int j = 1; j <= num[i]; ++j)
- --mv[edge[i][j]];
- num[i] = 0;
- }
- vector < int > tmp;
- res.clear ();
- for (int i = 1; i <= k; ++i)
- if (!used[i] && mv[i] == 0) {
- tmp.clear ();
- int cur = i;
- while (num[cur] == 1) {
- tmp.push_back (cur);
- used[cur] = true;
- cur = edge[cur][1];
- }
- tmp.push_back (cur);
- used[cur] = true;
- res.push_back (tmp);
- }
- //cout << "Test#:" << ++numtest << endl;
- cout << res.size() << endl;
- for (int i = 0; i < int (res.size ()); ++i) {
- cout << res[i].size();
- for (int j = 0; j < int (res[i].size ()); ++j)
- cout << " " << res[i][j];
- cout << endl;
- }
- cout << endl;
- cerr << "ok" << endl;
- }while(0);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement