oj.uz

답안 #589767

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
589767 2022-07-05T08:54:28 Z 반딧불(#8407) 로카히아 유적 (FXCUP3_lokahia) C++17
13 / 100
 977 ms 194116 KB 
#include "sungjin.h"
#include <bits/stdc++.h>

struct unionFind{
    int n;
    int par[4000002];

    void init(int _n){
        n = _n;
        for(int i=0; i<=n; i++) par[i] = i;
    }

    int find(int x){
        if(par[x] == x) return x;
        return par[x] = find(par[x]);
    }

    void merge(int x, int y){
        x = find(x), y = find(y);
        par[x] = y;
    }
};

namespace {
    const int xx[]={0, 0, 1, -1};
    const int yy[]={1, -1, 0, 0};

    unionFind dsu;

    int n, m, k;
    int board[2002][2002];
    bool able[2002][2002];
    int num[2002][2002], numCnt;
}

void dfsAble(int x, int y){
    able[x][y] = 0;
    for(int d=0; d<4; d++){
        int tx = x+xx[d], ty = y+yy[d];
        if(tx<0 || ty<0 || tx>n+1 || ty>m+1 || !able[tx][ty]) continue;
        if(board[x][y] & (1<<d)) continue;
        if(board[tx][ty] & (1<<(d^1))) continue;
        dfsAble(tx, ty);
    }
}

void dfsGroup(int x, int y, int g){
    num[x][y] = g;
//    printf("%d %d: %d\n", x, y, g);
    for(int d=0; d<4; d++){
        int tx = x+xx[d], ty = y+yy[d];
        if(!able[tx][ty] || num[tx][ty]) continue;
        dfsGroup(tx, ty, g);
    }
}

void Init(int N, int M, int W, int R[], int C[], int D[]){
	n = N, m = M, k = W;
	dsu.init(n*m);
	for(int i=0; i<k; i++){
        D[i]--;
        int x = R[i], y = C[i], d = D[i];
        board[x][y] |= (1<<d);
	}
    for(int i=0; i<=n+1; i++) for(int j=0; j<=m+1; j++) able[i][j] = 1;
    dfsAble(0, 0);
    for(int i=0; i<k; i++) able[R[i]][C[i]] = 1;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(!able[i][j] || num[i][j]) continue;
            dfsGroup(i, j, ++numCnt);
        }
    }
}

int WereSameTerritory(int R1, int C1, int R2, int C2) {
	if(!able[R1][C1] || !able[R2][C2] || num[R1][C1] != num[R2][C2]) return false;
	return true;
}

#include "dowoon.h"
#include <bits/stdc++.h>

using namespace std;

namespace {
    const int xx[]={0, 0, 1, -1};
    const int yy[]={1, -1, 0, 0};

    int n, m;
    int link[2002][2002][4];
    int visited[2002][2002];
    int ans;
    int cnt;
}

void dfs(int x, int y){
    visited[x][y] = 1;
    cnt++;
    for(int d=0; d<4; d++){
        int tx = x+xx[d], ty = y+yy[d];
        if(!link[x][y][d] || visited[tx][ty]) continue;
        dfs(tx, ty);
    }
}

int Guess(int N, int M){
//    for(int i=1; i<=60000; i++){
//        printf("");
//    }
    n = N, m = M;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(i<n) link[i][j][2] = link[i+1][j][3] = Ask(i, j, i+1, j);
            if(j<m) link[i][j][0] = link[i][j+1][1] = Ask(i, j, i, j+1);
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(!visited[i][j]){
                cnt = 0;
                dfs(i, j);
                ans = max(ans, cnt);
            }
        }
    }
    return ans*2 > n*m;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 800 KB Correct
2 Correct 1 ms 792 KB Correct
3 Correct 13 ms 1432 KB Correct
4 Correct 52 ms 21440 KB Correct
5 Correct 55 ms 15444 KB Correct
6 Correct 232 ms 123720 KB Correct
7 Correct 256 ms 127108 KB Correct
8 Correct 279 ms 194116 KB Correct
9 Correct 264 ms 124704 KB Correct

Subtask #2
0 / 87.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 800 KB Correct
2 Correct 1 ms 792 KB Correct
3 Correct 13 ms 1432 KB Correct
4 Correct 52 ms 21440 KB Correct
5 Correct 55 ms 15444 KB Correct
6 Correct 232 ms 123720 KB Correct
7 Correct 256 ms 127108 KB Correct
8 Correct 279 ms 194116 KB Correct
9 Correct 264 ms 124704 KB Correct
10 Partially correct 558 ms 53596 KB Partially correct : C/MN = 1.550
11 Partially correct 42 ms 4888 KB Partially correct : C/MN = 1.500
12 Partially correct 18 ms 2900 KB Partially correct : C/MN = 1.467
13 Partially correct 5 ms 924 KB Partially correct : C/MN = 1.417
14 Partially correct 1 ms 648 KB Partially correct : C/MN = 1.333
15 Partially correct 1 ms 652 KB Partially correct : C/MN = 1.300
16 Partially correct 1 ms 656 KB Partially correct : C/MN = 1.250
17 Partially correct 0 ms 648 KB Partially correct : C/MN = 1.167
18 Correct 0 ms 656 KB Correct
19 Partially correct 977 ms 101756 KB Partially correct : C/MN = 1.600
20 Correct 1 ms 812 KB Correct
21 Runtime error 1 ms 340 KB Execution failed because the return code was nonzero
22 Halted 0 ms 0 KB -