oj.uz

Submission #589714

# Submission time Handle Problem Language Result Execution time Memory
589714 2022-07-05T07:27:47 Z 조영욱(#8409) Lokahian Rampart (FXCUP3_lokahia) C++17
13 / 100
 953 ms 104880 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[i];
        int y=C[i];
        int d=dir[i]-1;
        val[x][y][d]=1;
        //printf("...%d %d %d\n",x,y,dir[w]);
        val[x+dx[d]][y+dy[d]][d^1]=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]==0) {
                    int x=i+dx[k];
                    int y=j+dy[k];
                    if (x>=0&&x<=n+1&&y>=0&&y<=m+1) {
                        merge(i*(m+2)+j,x*(m+2)+y);
                        //printf(".%d %d %d %d\n",i,j,x,y);
                    }
                }
            }
        }
	}
}

int WereSameTerritory(int R1, int C1, int R2, int C2) {
    //printf("..%d %d %d %d %d %d\n",R1,C1,R2,C2,find(R1*(m+2)+C1)!=find(0),find(R2*(m+2)+C2)!=find(0));
	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) {
    memset(p,-1,sizeof(p));
    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
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8468 KB Correct
2 Correct 4 ms 8596 KB Correct
3 Correct 14 ms 8896 KB Correct
4 Correct 52 ms 15088 KB Correct
5 Correct 62 ms 14944 KB Correct
6 Correct 214 ms 59452 KB Correct
7 Correct 219 ms 62364 KB Correct
8 Correct 275 ms 94272 KB Correct
9 Correct 214 ms 55132 KB Correct

Subtask #2
0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8468 KB Correct
2 Correct 4 ms 8596 KB Correct
3 Correct 14 ms 8896 KB Correct
4 Correct 52 ms 15088 KB Correct
5 Correct 62 ms 14944 KB Correct
6 Correct 214 ms 59452 KB Correct
7 Correct 219 ms 62364 KB Correct
8 Correct 275 ms 94272 KB Correct
9 Correct 214 ms 55132 KB Correct
10 Partially correct 512 ms 57592 KB Partially correct : C/MN = 1.550
11 Partially correct 33 ms 8092 KB Partially correct : C/MN = 1.500
12 Partially correct 25 ms 6460 KB Partially correct : C/MN = 1.467
13 Partially correct 6 ms 4892 KB Partially correct : C/MN = 1.417
14 Partially correct 4 ms 4616 KB Partially correct : C/MN = 1.333
15 Partially correct 4 ms 4692 KB Partially correct : C/MN = 1.300
16 Partially correct 2 ms 4616 KB Partially correct : C/MN = 1.250
17 Partially correct 2 ms 4496 KB Partially correct : C/MN = 1.167
18 Correct 4 ms 4500 KB Correct
19 Partially correct 953 ms 104880 KB Partially correct : C/MN = 1.600
20 Correct 4 ms 8468 KB Correct
21 Runtime error 2 ms 4308 KB Execution failed because the return code was nonzero
22 Halted 0 ms 0 KB -