Submission #22329

#	Time	Username	Problem	Language	Result	Execution time	Memory
22329		버거킹 송죽SK점 우수고객 (#40)	Young Zebra (KRIII5_YZ)	C++14	2 / 7	23 ms	11596 KiB

YZ

#include<bits/stdc++.h>
using namespace std;

int n, m, org[405][405];
int par[160005], cnt[160005], inf[160005], cc;
char a[405][405];

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

vector<pair<pair<int,int>,int> > edg;

bool valid (int X, int Y) {
	return (1<=X && X<=n && 1<=Y && Y<=m);
}

int Find (int X) {
	if(par[X] == X) return X;
	return par[X] = Find(par[X]);
}

int dfs (int X, int Y) {
	org[X][Y] = cc;
	int ret = 1;
	for(int i=0;i<4;i++) {
		int nx = X + dx[i], ny = Y + dy[i];
		if(valid(nx, ny) && a[X][Y] == a[nx][ny] && !org[nx][ny]) {
			ret += dfs(nx, ny);
		}
	}
	return ret;
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) {
		scanf("%s",a[i]+1);
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {
		if(org[i][j]) continue;
		cc++;
		par[cc] = cc;
		cnt[cc] = dfs(i, j);
	}
	for(int i=1;i<=n;i++) {
		if(a[i][1] != a[i][m]) continue;
		int A = org[i][1], B = org[i][m];
		if(A > B) swap(A, B);
		edg.push_back({{A, B}, 0});
	}
	for(int i=1;i<=m;i++) {
		if(a[1][i] != a[n][i]) continue;
		int A = org[1][i], B = org[n][i];
		if(A > B) swap(A, B);
		edg.push_back({{A, B}, 1});
	}
	sort(edg.begin(), edg.end());
	edg.erase(unique(edg.begin(), edg.end()), edg.end());
	for(auto &I : edg) {
		int A = I.first.first, B = I.first.second;
		A = Find(A); B = Find(B);
		if(A == B) inf[A] = 1;
		else {
			inf[A] |= inf[B];
			cnt[A] += cnt[B];
			par[B] = A;
		}
	}
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			int tmp = Find(org[i][j]);
			printf("%d ", cnt[tmp]);
		}
		puts("");
	}
}

Compilation message (stderr)

YZ.cpp: In function 'int main()':
YZ.cpp:36:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
YZ.cpp:38:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",a[i]+1);
                     ^

• Subtask 1: 2 / 7