Submission #22454

#TimeUsernameProblemLanguageResultExecution timeMemory
22454AcornCkiGs14004Team (#40)Young Zebra (KRIII5_YZ)C++11
7 / 7
179 ms13056 KiB
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>

using namespace std;
typedef long long ll;
typedef pair<int, int> Pi;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) x.begin(), x.end()

int N, M;
int A[440][440];

int p[170070], z[170070];
int Find(int x){return p[x] == x ? x : p[x] = Find(p[x]); }

inline int idx(int x, int y){ return x * M + y; }
int ans[440][440];
int chk[170070];

typedef pair<int, int> pii;

set <pii> S;

inline int get_color(int x, int y){
	x %= N; if(x < 0) x += N;
	y %= M; if(y < 0) y += M;
	return A[x][y];
}

int bfs(int x, int mx){
	S.clear();
	queue <pii> que;
	que.push(pii(x/M, x%M));
	S.insert(pii(x/M, x%M));
	int cnt = 1;
	int xx[4] = {1, 0, -1, 0};
	int yy[4] = {0, 1, 0, -1};
	while(!que.empty()){
		pii t = que.front(); que.pop();
		int a = get_color(t.Fi, t.Se);
		rep(k, 4){
			int tx = t.Fi + xx[k];
			int ty = t.Se + yy[k];
			if(get_color(tx, ty) != a) continue;
			if(S.find(pii(tx, ty)) != S.end()) continue;
			S.insert(pii(tx, ty));
			que.push(pii(tx, ty));
			++cnt;
			if(cnt > mx) return 0;
		}
	}
	return 1;
}

void solve(int tc){
	scanf("%d%d", &N, &M);
	rep(i, N){
		char ch[440]; scanf("%s", ch);
		rep(j, M)A[i][j] = ch[j] == 'B';
	}
	rep(i, N*M)z[i] = 1, p[i] = i;
	rep(i, N)rep(j, M){
		int xx[2] = {0, 1};
		int yy[2] = {1, 0};
		rep(k, 2){
			int x = (i + N - xx[k]) % N;
			int y = (j + M - yy[k]) % M;
			if(A[i][j] != A[x][y]) continue;
			int a = idx(i, j);
			int b = idx(x, y);
			a = Find(a), b = Find(b);
			if(a != b)p[a] = b, z[b] += z[a];
		}
	}
	for(int i=0;i<N*M;i++)if(Find(i) == i){
		int t = bfs(i, z[i]);
		chk[i] = t;
	}
	for(int i=0;i<N*M;i++){
		ans[i/M][i%M] = (chk[Find(i)] == 0 ? -1 : z[Find(i)]);
	}
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++)printf("%d ", ans[i][j]); puts("");
	}
}

int main(){
	int Tc = 1; //scanf("%d", &Tc);
	for(int tc=1; tc<=Tc; tc++){
		solve(tc);
	}
	return 0;
}

Compilation message (stderr)

YZ.cpp: In function 'void solve(int)':
YZ.cpp:71: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:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char ch[440]; scanf("%s", ch);
                                ^
#Verdict Execution timeMemoryGrader output
Fetching results...