oj.uz

Submission #589718

# Submission time Handle Problem Language Result Execution time Memory
589718 2022-07-05T07:44:37 Z 반딧불(#8407) Lokahian Rampart (FXCUP3_lokahia) C++17
13 / 100
 1076 ms 198060 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] || (board[x][y] & (1<<d))) continue;
        if(num[tx][ty]){
            dsu.merge(g, 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=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] || dsu.find(num[R1][C1]) != dsu.find(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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 796 KB Correct
2 Correct 1 ms 932 KB Correct
3 Correct 12 ms 1532 KB Correct
4 Correct 64 ms 23636 KB Correct
5 Correct 98 ms 19400 KB Correct
6 Correct 315 ms 153248 KB Correct
7 Correct 302 ms 156900 KB Correct
8 Correct 332 ms 198060 KB Correct
9 Correct 283 ms 171464 KB Correct

Subtask #2
0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 796 KB Correct
2 Correct 1 ms 932 KB Correct
3 Correct 12 ms 1532 KB Correct
4 Correct 64 ms 23636 KB Correct
5 Correct 98 ms 19400 KB Correct
6 Correct 315 ms 153248 KB Correct
7 Correct 302 ms 156900 KB Correct
8 Correct 332 ms 198060 KB Correct
9 Correct 283 ms 171464 KB Correct
10 Partially correct 582 ms 53704 KB Partially correct : C/MN = 1.550
11 Partially correct 37 ms 4584 KB Partially correct : C/MN = 1.500
12 Partially correct 20 ms 3012 KB Partially correct : C/MN = 1.467
13 Partially correct 5 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.300
16 Partially correct 1 ms 652 KB Partially correct : C/MN = 1.250
17 Partially correct 0 ms 648 KB Partially correct : C/MN = 1.167
18 Correct 2 ms 648 KB Correct
19 Partially correct 1076 ms 105748 KB Partially correct : C/MN = 1.600
20 Correct 2 ms 752 KB Correct
21 Runtime error 1 ms 468 KB Execution failed because the return code was nonzero
22 Halted 0 ms 0 KB -