| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 22758 | 2017-04-30T07:15:23 Z | 퍼플달고싶다(#990, smu201111192, pce913, cokcjswo) | Young Zebra (KRIII5_YZ) | C++ | 486 ms | 39328 KB |
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define SIZE 31600000
#define BC 50
#define BS 5000
#define MOD 1000000007LL
#define MAXV 555
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef vector<vector<long long> > mat;
int n,m;
char str[444][444];
bool bd[1222][1222];
bool visited[1222][1222];
int sz[1222][1222];
pair<int, int> p[1222][1222];
int dy[4] = {-1,0,1,0}, dx[4] = {0,1,0,-1};
pair<int, int> find(pair<int, int> u) {
if(p[u.fi][u.se] == u) return u;
return p[u.fi][u.se] = find(p[u.fi][u.se]);
}
void merge(pair<int, int> u, pair<int, int> v) {
u = find(u), v = find(v);
if(u == v) return;
p[u.fi][u.se] = v;
sz[v.fi][v.se] += sz[u.fi][u.se];
}
bool ok(int y, int x) {return y>=0 && y<3*n && x>=0 && x<3*m;}
void bfs(int y, int x) {
queue<pair<int, int > > q;
q.push({y,x});
visited[y][x] = 1;
while(!q.empty()) {
int hy = q.front().fi, hx = q.front().se;
// printf("here %d %d\n",hy,hx);
q.pop();
for(int i=0;i<4;i++) {
int ny = hy + dy[i], nx = hx + dx[i];
if(ny < 0) ny += 3*n;
if(nx < 0) nx += 3*m;
if(ny >= 3*n) ny -= 3*n;
if(nx >= 3*m) nx -= 3*m;
if(ok(ny,nx) && visited[ny][nx] == 0 && (bd[y][x] == bd[ny][nx])) {
merge({y,x}, {ny,nx}), q.push({ny,nx}), visited[ny][nx] = 1;
}
}
}
}
int main () {
for(int i=0;i<1222;i++) for(int j=0;j<1222;j++) p[i][j] = {i,j}, sz[i][j] = 1;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%s",str[i]);
for(int yc=0;yc<3;yc++)
for(int xc=0;xc<3;xc++)
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
bd[yc*n+i][xc*m+j] = str[i][j] == 'B' ? 1 : 0;
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
int y = n+i, x = m+j;
if(visited[y][x] == 0) bfs(y,x);
pair<int, int> root = find({y,x});
printf("%d ",sz[root.fi][root.se]);
}
printf("\n");
}
// for(int i=0;i<100;i++) {
// for(int j=0;j<100;j++) printf("%d ",sz[i][j]);
// printf("\n");
// }
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Partially correct | 169 ms | 29032 KB | Output is partially correct |
| 2 | Partially correct | 179 ms | 37756 KB | Output is partially correct |
| 3 | Partially correct | 149 ms | 27484 KB | Output is partially correct |
| 4 | Partially correct | 136 ms | 25448 KB | Output is partially correct |
| 5 | Partially correct | 113 ms | 24560 KB | Output is partially correct |
| 6 | Partially correct | 73 ms | 23448 KB | Output is partially correct |
| 7 | Partially correct | 486 ms | 28112 KB | Output is partially correct |
| 8 | Partially correct | 199 ms | 39328 KB | Output is partially correct |
| 9 | Partially correct | 423 ms | 39308 KB | Output is partially correct |
| 10 | Partially correct | 123 ms | 24400 KB | Output is partially correct |
| 11 | Partially correct | 113 ms | 24992 KB | Output is partially correct |
| 12 | Partially correct | 99 ms | 24996 KB | Output is partially correct |
| 13 | Partially correct | 296 ms | 26708 KB | Output is partially correct |
| 14 | Partially correct | 179 ms | 26876 KB | Output is partially correct |
| 15 | Partially correct | 293 ms | 35628 KB | Output is partially correct |
| 16 | Partially correct | 173 ms | 24156 KB | Output is partially correct |
| 17 | Partially correct | 153 ms | 26304 KB | Output is partially correct |
| 18 | Partially correct | 69 ms | 26216 KB | Output is partially correct |
| 19 | Correct | 43 ms | 22632 KB | Output is correct |
| 20 | Partially correct | 253 ms | 39268 KB | Output is partially correct |
| 21 | Partially correct | 306 ms | 27448 KB | Output is partially correct |
| 22 | Partially correct | 389 ms | 27332 KB | Output is partially correct |
| 23 | Partially correct | 236 ms | 37732 KB | Output is partially correct |
| 24 | Partially correct | 196 ms | 32984 KB | Output is partially correct |
| 25 | Partially correct | 209 ms | 30808 KB | Output is partially correct |
| 26 | Partially correct | 13 ms | 22632 KB | Output is partially correct |
| 27 | Partially correct | 9 ms | 22632 KB | Output is partially correct |
| 28 | Partially correct | 9 ms | 22900 KB | Output is partially correct |
| 29 | Partially correct | 13 ms | 22904 KB | Output is partially correct |
| 30 | Partially correct | 6 ms | 22632 KB | Output is partially correct |
| 31 | Partially correct | 3 ms | 22632 KB | Output is partially correct |
| 32 | Partially correct | 13 ms | 22632 KB | Output is partially correct |
| 33 | Partially correct | 13 ms | 22632 KB | Output is partially correct |
| 34 | Partially correct | 9 ms | 22632 KB | Output is partially correct |
| 35 | Partially correct | 6 ms | 22632 KB | Output is partially correct |
| 36 | Partially correct | 19 ms | 23952 KB | Output is partially correct |
| 37 | Partially correct | 26 ms | 23732 KB | Output is partially correct |
| 38 | Correct | 9 ms | 22632 KB | Output is correct |
| 39 | Partially correct | 23 ms | 23720 KB | Output is partially correct |
| 40 | Partially correct | 16 ms | 23956 KB | Output is partially correct |