oj.uz

답안 #589708

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
589708 2022-07-05T07:18:07 Z 이동현(#8410) 로카히아 유적 (FXCUP3_lokahia) C++17
13 / 100
 1010 ms 172888 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};
vector<pair<int, int>>del;

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);
            }
            else{
                chk[nx][ny] = 1;
                del.push_back({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);
                while((int)del.size()){
                    chk[del.back().first][del.back().second] = 0;
                    del.pop_back();
                }
            }
        }
    }
	return (ans * 2 > N * M ? 1 : 0);
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 16456 KB Correct
2 Correct 6 ms 16644 KB Correct
3 Correct 21 ms 17276 KB Correct
4 Correct 63 ms 34808 KB Correct
5 Correct 56 ms 28628 KB Correct
6 Correct 291 ms 127332 KB Correct
7 Correct 298 ms 128848 KB Correct
8 Correct 298 ms 172888 KB Correct
9 Correct 314 ms 111868 KB Correct

Subtask #2
0 / 87.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 16456 KB Correct
2 Correct 6 ms 16644 KB Correct
3 Correct 21 ms 17276 KB Correct
4 Correct 63 ms 34808 KB Correct
5 Correct 56 ms 28628 KB Correct
6 Correct 291 ms 127332 KB Correct
7 Correct 298 ms 128848 KB Correct
8 Correct 298 ms 172888 KB Correct
9 Correct 314 ms 111868 KB Correct
10 Partially correct 624 ms 69392 KB Partially correct : C/MN = 1.550
11 Partially correct 43 ms 20108 KB Partially correct : C/MN = 1.312
12 Partially correct 28 ms 18292 KB Partially correct : C/MN = 1.467
13 Partially correct 13 ms 16668 KB Partially correct : C/MN = 1.417
14 Partially correct 9 ms 16372 KB Partially correct : C/MN = 1.111
15 Partially correct 9 ms 16396 KB Partially correct : C/MN = 1.100
16 Partially correct 8 ms 16356 KB Partially correct : C/MN = 1.250
17 Correct 9 ms 16404 KB Correct
18 Correct 6 ms 16400 KB Correct
19 Partially correct 1010 ms 116644 KB Partially correct : C/MN = 1.400
20 Correct 9 ms 16532 KB Correct
21 Runtime error 1 ms 468 KB Execution failed because the return code was nonzero
22 Halted 0 ms 0 KB -