# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
22789 | dried chocochip on Daegu asphalt (#40) | Young Zebra (KRIII5_YZ) | C++11 | 500 ms | 202368 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |