oj.uz

Submission #739005

# Submission time Handle Problem Language Result Execution time Memory
739005 2023-05-09T18:24:12 Z rainboy Colors (RMI18_colors) C
68 / 100
 333 ms 12532 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	150000

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 83 ms 340 KB Output is correct
2 Correct 30 ms 340 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 68 ms 372 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 324 KB Output is correct
2 Correct 30 ms 328 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 87 ms 324 KB Output is correct
2 Correct 30 ms 328 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 183 ms 472 KB Output is correct
5 Correct 275 ms 4176 KB Output is correct
6 Correct 333 ms 12032 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 340 KB Output is correct
2 Correct 30 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 87 ms 324 KB Output is correct
5 Correct 30 ms 328 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 87 ms 364 KB Output is correct
8 Correct 33 ms 476 KB Output is correct
9 Correct 3 ms 420 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 476 KB Output is correct
2 Correct 258 ms 4264 KB Output is correct
3 Correct 304 ms 12532 KB Output is correct

Subtask #7
0 / 10.0

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

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 340 KB Output is correct
2 Correct 30 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 68 ms 372 KB Output is correct
5 Correct 87 ms 324 KB Output is correct
6 Correct 30 ms 328 KB Output is correct
7 Correct 4 ms 340 KB Output is correct
8 Correct 183 ms 472 KB Output is correct
9 Correct 275 ms 4176 KB Output is correct
10 Correct 333 ms 12032 KB Output is correct
11 Correct 87 ms 364 KB Output is correct
12 Correct 33 ms 476 KB Output is correct
13 Correct 3 ms 420 KB Output is correct
14 Correct 175 ms 476 KB Output is correct
15 Correct 258 ms 4264 KB Output is correct
16 Correct 304 ms 12532 KB Output is correct
17 Incorrect 33 ms 384 KB Output isn't correct
18 Halted 0 ms 0 KB -