oj.uz

Submission #485867

# Submission time Handle Problem Language Result Execution time Memory
485867 2021-11-09T14:51:48 Z rainboy KOVANICE (COI15_kovanice) C
100 / 100
 228 ms 39008 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	300000
#define M	300000

int max(int a, int b) { return a > b ? a : b; }

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;
	}
}

void append(int **ej, int *eo, 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 *ej[N], eo[N], *fi[N], fo[N], dd[N], dp[N], dq[N];

void dfs(int **ej, int *eo, int *dp, int i) {
	if (dd[i] == 0) {
		int o;

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

			dp[j] = max(dp[j], dp[i] + 1), dd[j]--;
			dfs(ej, eo, dp, j);
		}
	}
}

int main() {
	static int ii[M], jj[M];
	int n, m, k, h, i, j;

	scanf("%d%d%d", &k, &n, &m);
	memset(ds, -1, n * sizeof *ds);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (j = 0; j < n; j++)
		fi[j] = (int *) malloc(2 * sizeof *fi[j]);
	for (h = 0; h < m; h++) {
		char c;

		scanf("%d%c%d", &i, &c, &j), i--, j--;
		if (c == '=')
			join(i, j), ii[h] = jj[h] = -1;
		else if (c == '<')
			ii[h] = i, jj[h] = j;
		else
			ii[h] = j, jj[h] = i;
	}
	for (h = 0; h < m; h++) {
		i = ii[h], j = jj[h];
		if (i == -1)
			continue;
		i = find(i), j = find(j);
		append(ej, eo, i, j), append(fi, fo, j, i);
	}
	for (i = 0; i < n; i++)
		if (ds[i] < 0)
			dd[i] = fo[i];
	for (i = 0; i < n; i++)
		if (ds[i] < 0)
			dfs(ej, eo, dp, i);
	for (i = 0; i < n; i++)
		if (ds[i] < 0)
			dd[i] = eo[i];
	for (i = 0; i < n; i++)
		if (ds[i] < 0)
			dfs(fi, fo, dq, i);
	for (i = 0; i < n; i++) {
		int p = dp[find(i)], q = dq[find(i)];

		if (p + 1 + q == k)
			printf("K%d\n", p + 1);
		else
			printf("?\n");
	}
	return 0;
}

Compilation message

kovanice.c: In function 'append':
kovanice.c:33:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   33 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
kovanice.c: In function 'main':
kovanice.c:58:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  scanf("%d%d%d", &k, &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
kovanice.c:67:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   scanf("%d%c%d", &i, &c, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 23156 KB Output is correct
2 Correct 72 ms 23184 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3244 KB Output is correct
2 Correct 23 ms 3160 KB Output is correct
3 Correct 21 ms 3068 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 39008 KB Output is correct
2 Correct 199 ms 38436 KB Output is correct
3 Correct 193 ms 38208 KB Output is correct
4 Correct 219 ms 37812 KB Output is correct
5 Correct 228 ms 38412 KB Output is correct