Submission #962047

#	Time	Username	Problem	Language	Result	Execution time	Memory
962047		riariti	CSS (COI14_css)	C++17	100 / 100	104 ms	49328 KiB

css

    #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 (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10