제출 #22848

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
22848		past future present (#40)	Young Zebra (KRIII5_YZ)	C++14	2 / 7	79 ms	17424 KiB

YZ

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

struct edge
{
	int t, w;
	edge(int t, int w) : t(t), w(w) {}
	bool operator <(const edge &o) const
	{
		return t < o.t;
	}

	bool operator == (const edge &o) const
	{
		return t == o.t;
	}
};

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;
vector<edge> gg[400 * 400];

int ans[400 * 400], v[400][400], nf;
long long 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 (auto e : gg[c])
	{
		if (e.t == p) continue;
		if (v1[e.t])
		{
			long long l = len[c] + e.w - len[e.t];
			if (l) cycle = true;
		}
		else
		{
			len[e.t] = len[c] + e.w;
			cycle |= bar(e.t, 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 < n; i++)
	{
		if (fl[i][0] != fl[i][m - 1]) continue;
		gg[v[i][0]].push_back(edge(v[i][m - 1],1));
		gg[v[i][m - 1]].push_back(edge(v[i][0],-1));
	}
	for (int i = 0; i < m; i++)
	{
		if (fl[0][i] != fl[n - 1][i]) continue;
		gg[v[0][i]].push_back(edge(v[n - 1][i],100000));
		gg[v[n - 1][i]].push_back(edge(v[0][i],-100000));
	}
	for (int i = 0; i <= nf; i++)
	{
		sort(gg[i].begin(), gg[i].end());
		gg[i].erase(unique(gg[i].begin(), gg[i].end()), gg[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("");
	}
}

컴파일 시 표준 에러 (stderr) 메시지

YZ.cpp: In function 'void foo(int, int)':
YZ.cpp:46:7: warning: unused variable 'y' [-Wunused-variable]
   int y = idx / m;
       ^
YZ.cpp:47:7: warning: unused variable 'x' [-Wunused-variable]
   int x = idx % m;
       ^
YZ.cpp: In function 'int main()':
YZ.cpp:87: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:90: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