oj.uz

Submission #589682

# Submission time Handle Problem Language Result Execution time Memory
589682 2022-07-05T06:23:22 Z 박상훈(#8406) Lokahian Rampart (FXCUP3_lokahia) C++17
30 / 100
 1105 ms 206664 KB 
#include "sungjin.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
static int dx[5] = {0, 0, 0, 1, -1}, dy[5] = {0, 1, -1, 0, 0};
static int a[1010][1010], n, m;
static bool iswall[1010][1010][5], no[1001000];

static void dfs0(int i, int j){
    a[i][j] = -1;
    for (int k=1;k<=4;k++){
        int nx = i+dx[k], ny = j+dy[k];
        if (nx<0 || nx>n+1 || ny<0 || ny>m+1) continue;
        if (a[nx][ny]!=-1 && !iswall[nx][ny][((k-1)^1)+1]) dfs0(nx, ny);
    }
}

static void dfs(int i, int j, int c){
    a[i][j] = c;
    for (int k=1;k<=4;k++){
        int nx = i+dx[k], ny = j+dy[k];
        if (a[nx][ny]==0) dfs(nx, ny, c);
    }
}

void Init(int N, int M, int W, int R[], int C[], int dir[]) {
    //return;

    n = N, m = M;
    //for (int i=0;i<=N+1;i++) fill(a[i], a[i]+M+2, -1);
    //for (int i=1;i<=N;i++) fill(a[i]+1, a[i]+M+1, 0);

    for (int i=0;i<W;i++){
        iswall[R[i]][C[i]][dir[i]] = 1;
        //a[R[i]+dx[dir[i]]][C[i]+dy[dir[i]]] = -1;
    }

    dfs0(0, 0);

    int cnt = 1;
    for (int i=1;i<=N;i++){
        for (int j=1;j<=M;j++) if (a[i][j]==0){
            dfs(i, j, cnt);
            cnt++;
        }
    }

    /*for (int i=1;i<=N;i++){
        for (int j=1;j<=M;j++) if (a[i][j]>0){
            for (int k=1;k<=4;k++){
                int nx = i+dx[k], ny = j+dy[k];
                if (a[nx][ny]==-1 && !iswall[i][j][k]) no[a[i][j]] = 1;
            }
        }
    }*/

    /*for (int i=1;i<=N;i++){
        for (int j=1;j<=M;j++) printf("%d ", a[i][j]);
        printf("\n");
    }*/
}

int WereSameTerritory(int R1, int C1, int R2, int C2) {
    //return 0;

	if (a[R1][C1]>0 && a[R1][C1]==a[R2][C2]) return 1;
	return 0;
}

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

using namespace std;
typedef long long ll;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0}, n, m;
int my_ans[1010][1010][4];
bool visited[1010][1010];

int is_edge(int x, int y, int k){
    int nx = x + dx[k], ny = y + dy[k];
    if (nx<=0 || nx>n) return 0;
    if (ny<=0 || ny>m) return 0;
    if (my_ans[x][y][k]>=0) return my_ans[x][y][k];

    int ret = Ask(x, y, nx, ny);
    my_ans[x][y][k] = ret;
    my_ans[nx][ny][k^1] = ret;
    return ret;
}

int cnt;
void dfs(int i, int j){
    visited[i][j] = 1;
    cnt++;
    for (int k=0;k<4;k++){
        int nx = i+dx[k], ny = j+dy[k];
        if (!visited[nx][ny] && is_edge(i, j, k)) dfs(nx, ny);
    }
}

int Guess(int N, int M) {
    //return 0;

	n = N, m = M;
	for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) fill(my_ans[i][j], my_ans[i][j]+4, -1);
	}

	int ans = 0;
	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);
        }
	}
	if (ans*2 > n*m) return 1;
	return 0;
}

Compilation message

sungjin.cpp:8:36: warning: 'no' defined but not used [-Wunused-variable]
    8 | static bool iswall[1010][1010][5], no[1001000];
      |                                    ^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 784 KB Correct
2 Correct 1 ms 792 KB Correct
3 Correct 15 ms 1392 KB Correct
4 Correct 59 ms 18180 KB Correct
5 Correct 54 ms 13704 KB Correct
6 Correct 243 ms 102156 KB Correct
7 Correct 219 ms 104876 KB Correct
8 Correct 308 ms 169872 KB Correct
9 Correct 251 ms 108468 KB Correct

Subtask #2
17.0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 784 KB Correct
2 Correct 1 ms 792 KB Correct
3 Correct 15 ms 1392 KB Correct
4 Correct 59 ms 18180 KB Correct
5 Correct 54 ms 13704 KB Correct
6 Correct 243 ms 102156 KB Correct
7 Correct 219 ms 104876 KB Correct
8 Correct 308 ms 169872 KB Correct
9 Correct 251 ms 108468 KB Correct
10 Partially correct 656 ms 53612 KB Partially correct : C/MN = 1.550
11 Partially correct 42 ms 4920 KB Partially correct : C/MN = 1.312
12 Partially correct 20 ms 2896 KB Partially correct : C/MN = 1.467
13 Partially correct 3 ms 932 KB Partially correct : C/MN = 1.417
14 Partially correct 2 ms 648 KB Partially correct : C/MN = 1.333
15 Partially correct 2 ms 660 KB Partially correct : C/MN = 1.100
16 Partially correct 1 ms 656 KB Partially correct : C/MN = 1.250
17 Correct 0 ms 648 KB Correct
18 Correct 2 ms 648 KB Correct
19 Partially correct 1105 ms 110692 KB Partially correct : C/MN = 1.440
20 Correct 1 ms 796 KB Correct
21 Partially correct 1 ms 876 KB Partially correct : C/MN = 1.460
22 Partially correct 3 ms 796 KB Partially correct : C/MN = 1.480
23 Partially correct 4 ms 1072 KB Partially correct : C/MN = 1.038
24 Partially correct 12 ms 16440 KB Partially correct : C/MN = 1.039
25 Partially correct 16 ms 3252 KB Partially correct : C/MN = 1.558
26 Partially correct 19 ms 4836 KB Partially correct : C/MN = 1.195
27 Partially correct 60 ms 5992 KB Partially correct : C/MN = 1.399
28 Partially correct 55 ms 4556 KB Partially correct : C/MN = 1.131
29 Partially correct 64 ms 20100 KB Partially correct : C/MN = 1.112
30 Partially correct 81 ms 18740 KB Partially correct : C/MN = 1.166
31 Partially correct 265 ms 129788 KB Partially correct : C/MN = 1.153
32 Partially correct 245 ms 122368 KB Partially correct : C/MN = 1.284
33 Partially correct 277 ms 73064 KB Partially correct : C/MN = 1.397
34 Partially correct 276 ms 117636 KB Partially correct : C/MN = 1.298
35 Partially correct 364 ms 99024 KB Partially correct : C/MN = 1.998
36 Correct 345 ms 206664 KB Correct
37 Partially correct 321 ms 24824 KB Partially correct : C/MN = 1.630
38 Partially correct 369 ms 25140 KB Partially correct : C/MN = 1.778
39 Partially correct 230 ms 22256 KB Partially correct : C/MN = 1.239
40 Partially correct 219 ms 23272 KB Partially correct : C/MN = 1.292
41 Partially correct 288 ms 85844 KB Partially correct : C/MN = 1.204
42 Partially correct 344 ms 60376 KB Partially correct : C/MN = 1.998
43 Partially correct 317 ms 52352 KB Partially correct : C/MN = 1.498
44 Partially correct 111 ms 13316 KB Partially correct : C/MN = 1.600
45 Partially correct 139 ms 13252 KB Partially correct : C/MN = 1.600
46 Partially correct 337 ms 35308 KB Partially correct : C/MN = 1.499