oj.uz

Submission #485196

# Submission time Handle Problem Language Result Execution time Memory
485196 2021-11-06T14:15:46 Z rainboy CSS (COI14_css) C
100 / 100
 158 ms 37400 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	5000
#define M	5000000
#define K	5000
#define Q	5
#define L	8192

int *ej[N], eo[N], ll[N], rr[N], pp[N]; char *ss[N];
int ll_[Q][K], rr_[Q][K], kk[Q]; char direct[Q][K];
char *tt[M]; int idx[M]; char used[M];

unsigned int X = 12345;

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

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

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

		while (j < k) {
			int c = strcmp(tt[hh[j]], tt[h]);

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

char dp[N][K]; int qu[N], cnt, g_;

int check(int l, int r) {
	int h;

	for (h = l; h < r; h++)
		if (!used[idx[h]])
			return 0;
	return 1;
}

void dfs(int p, int i) {
	int o, h;

	for (h = ll[i]; h < rr[i]; h++)
		used[idx[h]] = 1;
	memset(dp[i], 0, kk[g_] * sizeof *dp[i]);
	for (h = kk[g_] - 1; h >= 0; h--)
		if ((p == -1 ? h == 0 : dp[p][h])) {
			if (!direct[g_][h])
				dp[i][h] = 1;
			if (check(ll_[g_][h], rr_[g_][h])) {
				if (h + 1 == kk[g_])
					qu[cnt++] = i;
				else
					dp[i][h + 1] = 1;
			}
		}
	for (h = ll[i]; h < rr[i]; h++)
		used[idx[h]] = 0;
	for (o = 0; o < eo[i]; o++) {
		int j = ej[i][o];

		dfs(i, j);
	}
}

void filter(char *s) {
	int i, l_;

	l_ = 0;
	for (i = 0; s[i]; i++)
		if (s[i] != '\r')
			s[l_++] = s[i];
	s[l_] = 0;
}

int main() {
	static char buf[L];
	static int hh[M];
	int n, n_, m, q, g, h, i, i_, j, j_;

	fgets(buf, L, stdin), sscanf(buf, "%d", &n);
	n_ = 0, m = 0, cnt = 0;
	while (n--) {
		fgets(buf, L, stdin), filter(buf);
		if (buf[1] == 'd') {
			i = j = 9;
			while (buf[j] != '\'')
				j++;
			buf[j] = 0, ss[n_] = strdup(buf + i);
			i = j + 1;
			while (buf[i] != '\'')
				i++;
			ll[n_] = m;
			for (j = i + 1; buf[j] != '>'; j++)
				if (buf[j] == ' ' || buf[j] == '\'') {
					buf[j] = 0, tt[m++] = strdup(buf + i + 1);
					i = j;
				}
			rr[n_] = m;
			if (cnt)
				pp[n_] = qu[cnt - 1], append(qu[cnt - 1], n_);
			else
				pp[n_] = -1;
			ej[n_] = (int *) malloc(2 * sizeof *ej[n_]);
			qu[cnt++] = n_++;
		} else
			cnt--;
	}
	n = n_;
	fgets(buf, L, stdin), sscanf(buf, "%d", &q);
	for (g = 0; g < q; g++) {
		fgets(buf, L, stdin), filter(buf);
		for (i = -1, j = 0; buf[j]; j++)
			if (buf[j] == ' ' || buf[j] == '\n') {
				if (buf[i + 1] == '>')
					direct[g][kk[g]] = 1;
				else {
					ll_[g][kk[g]] = m;
					for (i_ = i + 1, j_ = i + 2; j_ <= j; j_++)
						if (j_ == j || buf[j_] == '.') {
							buf[j_] = 0, tt[m++] = strdup(buf + i_ + 1);
							i_ = j_;
						}
					rr_[g][kk[g]] = m;
					kk[g]++;
				}
				i = j;
			}
	}
	for (h = 0; h < m; h++)
		hh[h] = h;
	sort(hh, 0, m);
	for (h = 0, i = 0; h < m; h++)
		idx[hh[h]] = h + 1 == m || strcmp(tt[hh[h + 1]], tt[hh[h]]) != 0 ? i++ : i;
	for (g = 0; g < q; g++) {
		g_ = g, cnt = 0;
		for (i = 0; i < n; i++)
			if (pp[i] == -1)
				dfs(-1, i);
		printf("%d", cnt);
		for (h = 0; h < cnt; h++)
			printf(" %s", ss[qu[h]]);
		printf("\n");
	}
	return 0;
}

Compilation message

css.c: In function 'append':
css.c:24:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   24 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
css.c: In function 'main':
css.c:103:2: warning: ignoring return value of 'fgets' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |  fgets(buf, L, stdin), sscanf(buf, "%d", &n);
      |  ^~~~~~~~~~~~~~~~~~~~
css.c:106:3: warning: ignoring return value of 'fgets' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |   fgets(buf, L, stdin), filter(buf);
      |   ^~~~~~~~~~~~~~~~~~~~
css.c:132:2: warning: ignoring return value of 'fgets' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |  fgets(buf, L, stdin), sscanf(buf, "%d", &q);
      |  ^~~~~~~~~~~~~~~~~~~~
css.c:134:3: warning: ignoring return value of 'fgets' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |   fgets(buf, L, stdin), filter(buf);
      |   ^~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 21452 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 26608 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 36420 KB Output is correct
2 Correct 69 ms 26100 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 36544 KB Output is correct
2 Correct 64 ms 26128 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 36544 KB Output is correct
2 Correct 133 ms 26680 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 36604 KB Output is correct
2 Correct 79 ms 26308 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 36640 KB Output is correct
2 Correct 111 ms 26512 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 37400 KB Output is correct
2 Correct 77 ms 26160 KB Output is correct