oj.uz

Submission #739009

# Submission time Handle Problem Language Result Execution time Memory
739009 2023-05-09T18:29:43 Z rainboy Colors (RMI18_colors) C
68 / 100
 350 ms 12612 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	200000

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int *ej[N], eo[N];

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int aa[N * 2], xx[N * 2], yy[N * 2];

int compare_a(int i, int j) { return aa[i] - aa[j]; }
int compare_axy(int i, int j) { return aa[i] != aa[j] ? aa[i] - aa[j] : (xx[i] != xx[j] ? xx[i] - xx[j] : yy[i] - yy[j]); }

int (*compare)(int, int);

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k) {
			int c = compare(ii[j], i_);

			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}

int ds[N];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

void join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
}

char active[N];

void activate(int i) {
	int o;

	active[i] = 1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (active[j])
			join(i, j);
	}
}

int main() {
	int t;

	scanf("%d", &t);
	while (t--) {
		static int ii[N * 2];
		int n, m, h, i, j, hasa, hasb, yes;

		scanf("%d%d", &n, &m);
		for (i = 0; i < n * 2; i++)
			scanf("%d", &aa[i]);
		for (i = 0; i < n; i++)
			ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
		for (h = 0; h < m; h++) {
			scanf("%d%d", &i, &j), i--, j--;
			append(i, j), append(j, i);
		}
		yes = 1;
		for (i = 0; i < n; i++)
			if (aa[i] < aa[n + i]) {
				yes = 0;
				break;
			}
		if (!yes) {
			printf("0\n");
			continue;
		}
		for (i = 0; i < n * 2; i++)
			ii[i] = i;
		compare = compare_a, sort(ii, 0, n * 2);
		memset(active, 0, n * sizeof *active);
		memset(ds, -1, n * sizeof *ds);
		for (j = n * 2 - 1; j >= 0; j = i) {
			i = j;
			while (i >= 0 && aa[ii[i]] == aa[ii[j]]) {
				if (ii[i] < n)
					activate(ii[i]);
				i--;
			}
			for (h = j; h > i; h--)
				xx[ii[h]] = find(ii[h] < n ? ii[h] : ii[h] - n);
		}
		memset(active, 0, n * sizeof *active);
		memset(ds, -1, n * sizeof *ds);
		for (i = 0; i < n * 2; i = j) {
			j = i;
			while (j < n * 2 && aa[ii[j]] == aa[ii[i]]) {
				if (ii[j] >= n)
					activate(ii[j] - n);
				j++;
			}
			for (h = i; h < j; h++)
				yy[ii[h]] = find(ii[h] < n ? ii[h] : ii[h] - n);
		}
		compare = compare_axy, sort(ii, 0, n * 2);
		yes = 1;
		for (i = 0; i < n * 2; i = j) {
			j = i, hasa = 0, hasb = 0;
			while (j < n * 2 && compare(ii[j], ii[i]) == 0) {
				if (ii[j] < n)
					hasa = 1;
				else
					hasb = 1;
				j++;
			}
			if (hasb && !hasa) {
				yes = 0;
				break;
			}
		}
		printf("%d\n", yes);
		for (i = 0; i < n; i++)
			free(ej[i]);
	}
	return 0;
}

Compilation message

colors.c: In function 'append':
colors.c:18:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   18 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
colors.c: In function 'main':
colors.c:89:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |  scanf("%d", &t);
      |  ^~~~~~~~~~~~~~~
colors.c:94:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |   scanf("%d%d", &n, &m);
      |   ^~~~~~~~~~~~~~~~~~~~~
colors.c:96:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |    scanf("%d", &aa[i]);
      |    ^~~~~~~~~~~~~~~~~~~
colors.c:100:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |    scanf("%d%d", &i, &j), i--, j--;
      |    ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 340 KB Output is correct
2 Correct 31 ms 364 KB Output is correct
3 Correct 3 ms 340 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 392 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 340 KB Output is correct
2 Correct 40 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 340 KB Output is correct
2 Correct 40 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 186 ms 348 KB Output is correct
5 Correct 295 ms 4192 KB Output is correct
6 Correct 350 ms 12144 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 340 KB Output is correct
2 Correct 31 ms 364 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 91 ms 340 KB Output is correct
5 Correct 40 ms 340 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 91 ms 340 KB Output is correct
8 Correct 33 ms 348 KB Output is correct
9 Correct 4 ms 340 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 392 KB Output is correct
2 Correct 241 ms 4372 KB Output is correct
3 Correct 340 ms 12612 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 340 KB Output is correct
2 Correct 31 ms 364 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 69 ms 392 KB Output is correct
5 Correct 91 ms 340 KB Output is correct
6 Correct 40 ms 340 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 186 ms 348 KB Output is correct
9 Correct 295 ms 4192 KB Output is correct
10 Correct 350 ms 12144 KB Output is correct
11 Correct 91 ms 340 KB Output is correct
12 Correct 33 ms 348 KB Output is correct
13 Correct 4 ms 340 KB Output is correct
14 Correct 179 ms 392 KB Output is correct
15 Correct 241 ms 4372 KB Output is correct
16 Correct 340 ms 12612 KB Output is correct
17 Incorrect 32 ms 396 KB Output isn't correct
18 Halted 0 ms 0 KB -