Submission #22811

#	Time	Username	Problem	Language	Result	Execution time	Memory
22811		past future present (#40)	Young Zebra (KRIII5_YZ)	C++14	2 / 7	93 ms	13048 KiB

YZ

#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

char in[405];
bool fl[400][400], v1[400*400], v2[400*400];
int dx[4] = { -1,0,0,1 }, dy[4] = { 0,1,-1,0 }, n, m;
vector<int> g[400 * 400], cc;

int ans[400*400], v[400][400], nf, len[400*400];

inline int pti(int y, int x)
{
	return y*m + x;
}

void foo(int i, int j)
{
	if (v[i][j] != 0) return;
	nf++;
	v[i][j] = nf;
	queue<int> q;
	q.emplace(pti(i, j));
	while (!q.empty())
	{
		int idx = q.front();
		int y = idx / m;
		int x = idx % m;
		q.pop();
		ans[nf]++;
		for (int e : g[idx])
		{
			int yy = e / m, xx = e%m;
			if (v[yy][xx]) continue;
			v[yy][xx] = nf;
			q.emplace(e);
		}
	}
	return;
}

bool bar(int c, int p)
{
	v1[c] = v2[c] = true;
	cc.push_back(c);
	bool cycle = false;
	for (int e : g[c])
	{
		if (e == p) continue;
		if (v1[e])
		{
			int l = len[c] + 1 - len[e];
			if (l & 1) cycle = true;
		}
		else
		{
			len[e] = len[c] + 1;
			cycle |= bar(e, c);
		}
	}
	if (cycle) ans[c] = -1;
	v1[c] = false;
	return cycle;
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i=0;i<n;i++)
	{
		scanf("%s", in);
		for (int j = 0; j < m; j++)
			fl[i][j] = in[j] == 'B';
	}
	for(int i=0;i<n;i++)
		for (int j = 0; j < m; j++)
		{
			int p1 = pti(i, j);
			for (int d = 0; d < 4; d++)
			{
				int x = j + dx[d], y = i + dy[d];
				if (x < 0 || x >= m || y < 0 || y >= n) continue;
				if (fl[i][j] != fl[y][x]) continue;
				int p2 = pti(y, x);
				g[p1].push_back(p2);
			}
		}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			foo(i, j);
	for (int i = 0; i <= nf; i++) g[i].clear();
	for (int i = 0; i < n; i++)
	{
		if (fl[i][0] != fl[i][m - 1]) continue;
		g[v[i][0]].push_back(v[i][m - 1]);
		g[v[i][m - 1]].push_back(v[i][0]);
	}
	for (int i = 0; i < m; i++)
	{
		if (fl[0][i] != fl[n - 1][i]) continue;
		g[v[0][i]].push_back(v[n - 1][i]);
		g[v[n - 1][i]].push_back(v[0][i]);
	}
	for (int i = 0; i <= nf; i++)
	{
		sort(g[i].begin(), g[i].end());
		g[i].erase(unique(g[i].begin(), g[i].end()), g[i].end());
	}
	for (int i = 1; i <= nf; i++)
	{
		if (v2[i]) continue;
		v2[i] = true;
		len[i] = 0;
		cc.clear();
		bar(i,0);
		int sum = 0;
		sort(cc.begin(), cc.end());
		cc.erase(unique(cc.begin(), cc.end()), cc.end());
		for (int i : cc) sum += ans[i];
		if (sum < 0) sum = -1;
		for (int i : cc) ans[i] = sum;
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			printf("%d ", ans[v[i][j]]);
		}
		puts("");
	}
}

Compilation message (stderr)

YZ.cpp: In function 'void foo(int, int)':
YZ.cpp:29:7: warning: unused variable 'y' [-Wunused-variable]
   int y = idx / m;
       ^
YZ.cpp:30:7: warning: unused variable 'x' [-Wunused-variable]
   int x = idx % m;
       ^
YZ.cpp: In function 'int main()':
YZ.cpp:70:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
YZ.cpp:73:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", in);
                  ^

• Subtask 1: 2 / 7