oj.uz

Submission #72876

# Submission time Handle Problem Language Result Execution time Memory
72876 2018-08-27T07:01:45 Z ainta Lokahian Rampart (FXCUP3_lokahia) C++17
30 / 100
 1233 ms 185040 KB 
#include "sungjin.h"

static int X[1010][1010], Y[1010][1010], n, m, vis[1010][1010], U[1010][1010];

static int w[1010][1010][4], dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };

static int Rev[4] = { 1,0,3,2 };

void DFS(int x, int y) {
	if (x<0 || y<0 || x>n + 1 || y>m + 1 || vis[x][y])return;
	vis[x][y] = 1;
	for (int i = 0; i < 4; i++) {
		if(!w[x][y][i])DFS(x + dx[i], y + dy[i]);
	}
}


void Go(int x, int y, int col) {
	vis[x][y] = col;
	for (int i = 0; i < 4; i++) {
		int tx = x + dx[i], ty = y + dy[i];
		if(!vis[tx][ty])Go(x + dx[i], y + dy[i], col);
	}
}

void Init(int N, int M, int W, int R[], int C[], int dir[]) {
	int i, j, res = 0;
	n = N, m = M;
	for (i = 0; i < W; i++) {
		dir[i]--;
		w[R[i]+dx[dir[i]]][C[i]+dy[dir[i]]][Rev[dir[i]]] = 1;
	}
	DFS(0, 0);
	int cnt = 1;
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= M; j++) {
			if (!vis[i][j]) {
				cnt++;
				Go(i, j, cnt);
			}
		}
	}
}

int WereSameTerritory(int R1, int C1, int R2, int C2) {
	if (vis[R1][C1] == vis[R2][C2] && vis[R1][C1] != 1)return 1;
	return 0;
}

#include "dowoon.h"


int UF[1010000], C[1010000];

int nn, mm;

int Num(int x, int y) {
	return (x - 1)*mm + y;
}
int Find(int a) {
	if (a == UF[a])return a;
	return UF[a] = Find(UF[a]);
}
void Merge(int a, int b, int c, int d) {
	int x = Num(a, b), y = Num(c, d);
	x = Find(x), y = Find(y);
	if(x!=y)UF[x] = y;
}

/*void Put(int x, int y, int c) {
	if (w[x][y])return;
	tot++;
	w[x][y] = c;
	C[c]++;
}*/
int Guess(int N, int M) {
	int i, j;
	nn = N, mm = M;
/*	n = N, m = M;
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= M; j++) {
			if (w[i][j]) {
				if (w[i][j] == 1) continue;
				if (j + 1 <= M && !w[i][j + 1]) {
					if (Ask(i, j, i, j + 1))Put(i,j+1,w[i][j]);
					else Put(i,j+1,2);
				}
				if (i + 1 <= N && !w[i + 1][j]) {
					if (Ask(i, j, i + 1, j))Put(i+1,j,1);
					else Put(i+1,j,2);
				}
				continue;
			}
			if (i == N && j == M) {
				w[i][j] = 2;
				continue;
			}
			if (i == N) {
				if (Ask(i, j, i, j + 1)) {
					Put(i, j, 1);
					Put(i, j + 1, 1);
				}
				else Put(i, j, 2);
				continue;
			}
			if (j == M) {
				if (Ask(i, j, i + 1, j)) {
					Put(i, j, 1);
					Put(i + 1, j, 1);
				}
				else Put(i, j, 2);
				continue;
			}
			int t1 = Ask(i, j, i + 1, j);
			int t2 = Ask(i, j, i, j + 1);
			if (t1 || t2) {
				Put(i, j, 1);
				if (t1)Put(i + 1, j, 1);
				else Put(i + 1, j, 2);
				if (t2)Put(i, j + 1, 1);
				else Put(i, j + 1, 2);
			}
			else {
				Put(i, j, 2);
			}
		}
	}
	if (c1 * 2 > N*M)return 1;
	return 0;*/
	for(i=1;i<=N*M;i++)UF[i]=i;
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= M; j++) {
			if (i + 1 <= N && Ask(i, j, i + 1, j))Merge(i, j, i + 1, j);
			if (j + 1 <= M && Ask(i, j, i , j + 1))Merge(i, j, i, j + 1);
		}
	}
	for (i = 1; i <= N*M; i++)C[Find(i)]++;
	for (i = 1; i <= N*M; i++)if (C[i] * 2 > N*M)return 1;
	return 0;
}

Compilation message

sungjin.cpp: In function 'void Init(int, int, int, int*, int*, int*)':
sungjin.cpp:27:12: warning: unused variable 'res' [-Wunused-variable]
  int i, j, res = 0;
            ^~~
sungjin.cpp: At global scope:
sungjin.cpp:3:65: warning: 'U' defined but not used [-Wunused-variable]
 static int X[1010][1010], Y[1010][1010], n, m, vis[1010][1010], U[1010][1010];
                                                                 ^
sungjin.cpp:3:27: warning: 'Y' defined but not used [-Wunused-variable]
 static int X[1010][1010], Y[1010][1010], n, m, vis[1010][1010], U[1010][1010];
                           ^
sungjin.cpp:3:12: warning: 'X' defined but not used [-Wunused-variable]
 static int X[1010][1010], Y[1010][1010], n, m, vis[1010][1010], U[1010][1010];
            ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 752 KB Correct
2 Correct 5 ms 1080 KB Correct
3 Correct 21 ms 1492 KB Correct
4 Correct 92 ms 17688 KB Correct
5 Correct 96 ms 17688 KB Correct
6 Correct 399 ms 87228 KB Correct
7 Correct 317 ms 104452 KB Correct
8 Correct 437 ms 146052 KB Correct
9 Correct 322 ms 185040 KB Correct

Subtask #2
17.0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 752 KB Correct
2 Correct 5 ms 1080 KB Correct
3 Correct 21 ms 1492 KB Correct
4 Correct 92 ms 17688 KB Correct
5 Correct 96 ms 17688 KB Correct
6 Correct 399 ms 87228 KB Correct
7 Correct 317 ms 104452 KB Correct
8 Correct 437 ms 146052 KB Correct
9 Correct 322 ms 185040 KB Correct
10 Partially correct 817 ms 185040 KB Partially correct : C/MN = 1.550
11 Partially correct 49 ms 185040 KB Partially correct : C/MN = 1.500
12 Partially correct 26 ms 185040 KB Partially correct : C/MN = 1.467
13 Partially correct 7 ms 185040 KB Partially correct : C/MN = 1.417
14 Partially correct 5 ms 185040 KB Partially correct : C/MN = 1.333
15 Partially correct 5 ms 185040 KB Partially correct : C/MN = 1.300
16 Partially correct 5 ms 185040 KB Partially correct : C/MN = 1.250
17 Partially correct 4 ms 185040 KB Partially correct : C/MN = 1.167
18 Correct 4 ms 185040 KB Correct
19 Partially correct 1233 ms 185040 KB Partially correct : C/MN = 1.600
20 Correct 6 ms 185040 KB Correct
21 Partially correct 5 ms 185040 KB Partially correct : C/MN = 1.800
22 Partially correct 5 ms 185040 KB Partially correct : C/MN = 1.800
23 Partially correct 7 ms 185040 KB Partially correct : C/MN = 1.499
24 Partially correct 25 ms 185040 KB Partially correct : C/MN = 1.666
25 Partially correct 13 ms 185040 KB Partially correct : C/MN = 1.980
26 Partially correct 26 ms 185040 KB Partially correct : C/MN = 1.980
27 Partially correct 55 ms 185040 KB Partially correct : C/MN = 1.980
28 Partially correct 57 ms 185040 KB Partially correct : C/MN = 1.899
29 Partially correct 75 ms 185040 KB Partially correct : C/MN = 1.908
30 Partially correct 117 ms 185040 KB Partially correct : C/MN = 1.993
31 Partially correct 416 ms 185040 KB Partially correct : C/MN = 1.998
32 Partially correct 423 ms 185040 KB Partially correct : C/MN = 1.998
33 Partially correct 370 ms 185040 KB Partially correct : C/MN = 1.998
34 Partially correct 356 ms 185040 KB Partially correct : C/MN = 1.998
35 Partially correct 420 ms 185040 KB Partially correct : C/MN = 1.998
36 Partially correct 457 ms 185040 KB Partially correct : C/MN = 1.998
37 Partially correct 332 ms 185040 KB Partially correct : C/MN = 1.800
38 Partially correct 362 ms 185040 KB Partially correct : C/MN = 1.798
39 Partially correct 239 ms 185040 KB Partially correct : C/MN = 1.980
40 Partially correct 237 ms 185040 KB Partially correct : C/MN = 1.980
41 Partially correct 468 ms 185040 KB Partially correct : C/MN = 1.998
42 Partially correct 367 ms 185040 KB Partially correct : C/MN = 1.998
43 Partially correct 363 ms 185040 KB Partially correct : C/MN = 1.998
44 Partially correct 140 ms 185040 KB Partially correct : C/MN = 1.600
45 Partially correct 149 ms 185040 KB Partially correct : C/MN = 1.600
46 Partially correct 407 ms 185040 KB Partially correct : C/MN = 1.499