oj.uz

Submission #589695

# Submission time Handle Problem Language Result Execution time Memory
589695 2022-07-05T06:51:51 Z 조영욱(#8409) Lokahian Rampart (FXCUP3_lokahia) C++17
0 / 100
 285 ms 524288 KB 
#include "sungjin.h"
#include <bits/stdc++.h>
using namespace std;

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int val[1002][1002][4];
int n,m,w;
int p[1010000];

int find(int a) {
    return p[a]<0?a:p[a]=find(p[a]);
}

void merge(int a,int b) {
    a=find(a);
    b=find(b);
    if (a==b) {
        return;
    }
    p[b]=a;
}

void Init(int N, int M, int W, int R[], int C[], int dir[]) {
	n=N;
	m=M;
	w=W;
	memset(p,-1,sizeof(p));
	for(int i=0;i<w;i++){
        int x=R[w];
        int y=C[w];
        int d=dir[w]-1;
        val[x][y][d]=1;
        val[x+dx[d]][y+dy[d]][d^2]=1;
	}
	for(int i=0;i<=m;i++) {
        merge(i,i+1);
        merge((m+2)*(n+1)+i,(m+2)*(n+1)+i+1);
	}
	for(int i=0;i<=n;i++) {
        merge(i*(m+2),(i+1)*(m+2));
        merge(i*(m+2)+m+1,(i+1)*(m+2)+m+1);
	}
	for(int i=0;i<=n+1;i++){
        for(int j=0;j<=m+1;j++) {
            for(int k=0;k<4;k++) {
                if (val[i][j][k]==1) {
                    int x=i+dx[k];
                    int y=j+dy[k];
                    merge(i*(m+2)+j,x*(m+2)+y);
                }
            }
        }
	}
}

int WereSameTerritory(int R1, int C1, int R2, int C2) {
	return find(R1*(m+2)+C1)!=find(0)&&find(R2*(m+2)+C2)!=find(0);
}

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

int p[1010000];

int find(int a) {
    return p[a]<0?a:p[a]=find(p[a]);
}

void merge(int a,int b) {
    a=find(a);
    b=find(b);
    if (a==b) {
        return;
    }
    p[a]+=p[b];
    p[b]=a;
}

int Guess(int N, int M) {
    for(int i=1;i<=N;i++) {
        for(int j=1;j<M;j++) {
            if (Ask(i,j,i,j+1)) {
                merge(i*(M+1)+j,i*(M+1)+j+1);
            }
        }
    }
    for(int i=1;i<N;i++) {
        for(int j=1;j<=M;j++) {
            if (Ask(i,j,i+1,j)) {
                merge(i*(M+1)+j,(i+1)*(M+1)+j);
            }
        }
    }
    for(int i=1;i<=N;i++) {
        for(int j=1;j<=M;j++) {
            int now=i*(M+1)+j;
            if (-p[find(now)]*2>=N*M) {
                return 1;
            }
        }
    }
	return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 285 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 87.0

# Verdict Execution time Memory Grader output
1 Runtime error 285 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -