Submission #22789

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
22789	2017-04-30T07:29:47 Z	dried chocochip on Daegu asphalt(#897, suzy, zych1751, Acka)	Young Zebra (KRIII5_YZ)	C++11	0 / 7	500 ms	202368 KB

YZ

#include<bits/stdc++.h>

using namespace std;

int n, m;
char mmap[400][400];
int cc[400][400], c_idx;
bool visited[400][400];
int cc_sz[400*400+2];
int di[4] = {-1, 0, 1, 0};
int dj[4] = {0, 1, 0, -1};

int mod(int val, int m)
{
	return (val+m*m*m)%m;
}

map<pair<int,int>,int> mm;
int m_idx;

int pan(int i, int j)
{
	i += n*n*n;
	j += m*m*m;

	auto it = make_pair(i/n, j/m);
	if(mm.count(it) == 0)
		mm[it] = m_idx++;
	return mm[it];
}

void dfs(int i, int j)
{
	int ii = mod(i, n), jj = mod(j, m);
	visited[ii][jj] = true;
	cc[ii][jj] = c_idx;
	cc_sz[c_idx]++;

	for(int k = 0; k < 4; k++)
	{
		int ni = i+di[k], nj = j+dj[k];
		int nii = mod(ni, n), njj = mod(nj, m);

		if(!visited[nii][njj] && mmap[ii][jj] == mmap[nii][njj])
			dfs(ni, nj);
	}
}

int si, sj;
bool cc_inf[400*400+2];
bool vvisited[1000][400][400];

void dfs2(int i, int j)
{
	int ii = mod(i, n), jj = mod(j, m);
	int p = pan(i, j);
	vvisited[p][ii][jj] = true;

	if(cc_inf[cc[ii][jj]])	return;

	for(int k = 0; k < 4; k++)
	{
		int ni = i+di[k], nj = j+dj[k], np = pan(ni,nj);
		int nii = mod(ni, n), njj = mod(nj, m);

		if(!(ni == si && nj == sj) && (nii == si && njj == sj))
			cc_inf[cc[ii][jj]] = true;

		if(!vvisited[np][nii][njj] && mmap[ii][jj] == mmap[nii][njj])
			dfs2(ni, nj);
	}

}

int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			scanf(" %c", &mmap[i][j]);

	pan(0, 0);

	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
		{
			if(!visited[i][j])
			{
				c_idx++;
				dfs(i, j);
			}
			if(!vvisited[pan(i, j)][i][j])
			{
				si = i, sj = j;
				dfs2(i, j);
			}
		}

	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
			printf("%d ", cc_inf[cc[i][j]] ? -1 : cc_sz[cc[i][j]]);
		printf("\n");
	}
	return 0;
}

Compilation message

YZ.cpp: In function 'int main()':
YZ.cpp:77:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
YZ.cpp:80:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c", &mmap[i][j]);
                             ^

Subtask #1

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	500 ms	202368 KB	Execution timed out
2	Halted	0 ms	0 KB	-