oj.uz

Submission #738986

# Submission time Handle Problem Language Result Execution time Memory
738986 2023-05-09T18:14:30 Z rainboy Colors (RMI18_colors) C
68 / 100
 381 ms 19520 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);
		}
		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 93 ms 1728 KB Output is correct
2 Correct 31 ms 848 KB Output is correct
3 Correct 3 ms 468 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 2012 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 1712 KB Output is correct
2 Correct 35 ms 868 KB Output is correct
3 Correct 4 ms 468 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 1712 KB Output is correct
2 Correct 35 ms 868 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 190 ms 3376 KB Output is correct
5 Correct 292 ms 10444 KB Output is correct
6 Correct 381 ms 18968 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 1728 KB Output is correct
2 Correct 31 ms 848 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 93 ms 1712 KB Output is correct
5 Correct 35 ms 868 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 96 ms 1708 KB Output is correct
8 Correct 33 ms 844 KB Output is correct
9 Correct 4 ms 468 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 3400 KB Output is correct
2 Correct 266 ms 10100 KB Output is correct
3 Correct 363 ms 19520 KB Output is correct

Subtask #7
0 / 10.0

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

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 1728 KB Output is correct
2 Correct 31 ms 848 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 71 ms 2012 KB Output is correct
5 Correct 93 ms 1712 KB Output is correct
6 Correct 35 ms 868 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 190 ms 3376 KB Output is correct
9 Correct 292 ms 10444 KB Output is correct
10 Correct 381 ms 18968 KB Output is correct
11 Correct 96 ms 1708 KB Output is correct
12 Correct 33 ms 844 KB Output is correct
13 Correct 4 ms 468 KB Output is correct
14 Correct 197 ms 3400 KB Output is correct
15 Correct 266 ms 10100 KB Output is correct
16 Correct 363 ms 19520 KB Output is correct
17 Incorrect 35 ms 1124 KB Output isn't correct
18 Halted 0 ms 0 KB -