# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
22328 | 버거킹 송죽SK점 우수고객 (#40) | Young Zebra (KRIII5_YZ) | C++14 | 23 ms | 11592 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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("");
}
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |