oj.uz

답안 #589707

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
589707 2022-07-05T07:13:55 Z 이동현(#8410) 로카히아 유적 (FXCUP3_lokahia) C++17
13 / 100
 1033 ms 172940 KB 
#include "sungjin.h"
#include <bits/stdc++.h>
using namespace std;

const int NS = 1004;
int Way[1004][1004][4];
int Wx[4] = {-1, 0, 1, 0}, Wy[4] = {0, 1, 0, -1};
int Chk[1004][1004], Col[1004][1004], ColN;
int n, m;

void dfs(int x, int y){
    Chk[x][y] = 1;
    for(int i = 0; i < 4; ++i){
        int nx = x + Wx[i], ny = y + Wy[i];
        if(nx >= 0 && nx <= n + 1 && ny >= 0 && ny <= m + 1 && !Chk[nx][ny] && !Way[x][y][i]){
            dfs(nx, ny);
        }
    }
}

void dfs2(int x, int y){
    Col[x][y] = ColN;
    for(int i = 0; i < 4; ++i){
        int nx = x + Wx[i], ny = y + Wy[i];
        if(nx >= 0 && nx <= n + 1 && ny >= 0 && ny <= m + 1 && !Chk[nx][ny] && !Col[nx][ny]){
            dfs2(nx, ny);
        }
    }
}

void Init(int N, int M, int W, int R[], int C[], int dir[]) {
    n = N, m = M;
    for(int i = 0; i < W; ++i){
        if(dir[i] == 2) dir[i] = 3;
        else if(dir[i] == 3) dir[i] = 2;
        else if(dir[i] == 4) dir[i] = 0;
        Way[R[i]][C[i]][dir[i]] = 1;
        Way[R[i] + Wx[dir[i]]][C[i] + Wy[dir[i]]][(dir[i] + 2) % 4] = 1;
    }
    dfs(0, 0);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(!Chk[i][j] && !Col[i][j]){
                ++ColN;
                dfs2(i, j);
            }
        }
    }
	// ToDo
}

int WereSameTerritory(int R1, int C1, int R2, int C2) {
    return (Col[R1][C1] && Col[R1][C1] == Col[R2][C2] ? 1 : 0);
}

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

const int NS = 1004;
int chk[NS][NS];
int nn, mm;
int way[NS][NS][4];
int cnt;
int wx[4] = {-1, 0, 1, 0}, wy[4] = {0, 1, 0, -1};

void Dfs(int x, int y){
    chk[x][y] = 1; ++cnt;
    for(int i = 0; i < 4; ++i){
        int nx = x + wx[i], ny = y + wy[i];
        if(nx >= 1 && nx <= nn && ny >= 1 && ny <= mm && !chk[nx][ny]){
            if(way[x][y][i] == -1){
                way[x][y][i] = way[nx][ny][(i + 2) % 4] = Ask(x, y, nx, ny);
            }
            if(way[x][y][i] == 1){
                Dfs(nx, ny);
            }
        }
    }
}

int Guess(int N, int M) {
    memset(way, -1, sizeof(way));
    nn = N, mm = M;
    int ans = 0;
    for(int i = 1; i <= nn; ++i){
        for(int j = 1; j <= mm; ++j){
            if(!chk[i][j]){
                cnt = 0;
                Dfs(i, j);
                ans = max(ans, cnt);
            }
        }
    }
	return (ans * 2 > N * M ? 1 : 0);
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16532 KB Correct
2 Correct 9 ms 16660 KB Correct
3 Correct 24 ms 17152 KB Correct
4 Correct 66 ms 34076 KB Correct
5 Correct 67 ms 28484 KB Correct
6 Correct 288 ms 111608 KB Correct
7 Correct 300 ms 113180 KB Correct
8 Correct 351 ms 172940 KB Correct
9 Correct 255 ms 111832 KB Correct

Subtask #2
0 / 87.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16532 KB Correct
2 Correct 9 ms 16660 KB Correct
3 Correct 24 ms 17152 KB Correct
4 Correct 66 ms 34076 KB Correct
5 Correct 67 ms 28484 KB Correct
6 Correct 288 ms 111608 KB Correct
7 Correct 300 ms 113180 KB Correct
8 Correct 351 ms 172940 KB Correct
9 Correct 255 ms 111832 KB Correct
10 Partially correct 669 ms 69604 KB Partially correct : C/MN = 1.550
11 Partially correct 46 ms 20764 KB Partially correct : C/MN = 1.312
12 Partially correct 30 ms 18640 KB Partially correct : C/MN = 1.467
13 Partially correct 12 ms 16668 KB Partially correct : C/MN = 1.417
14 Partially correct 9 ms 16400 KB Partially correct : C/MN = 1.333
15 Partially correct 8 ms 16348 KB Partially correct : C/MN = 1.200
16 Partially correct 9 ms 16388 KB Partially correct : C/MN = 1.250
17 Correct 7 ms 16268 KB Correct
18 Correct 11 ms 16256 KB Correct
19 Partially correct 1033 ms 118136 KB Partially correct : C/MN = 1.480
20 Correct 9 ms 16524 KB Correct
21 Runtime error 1 ms 468 KB Execution failed because the return code was nonzero
22 Halted 0 ms 0 KB -