| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 962047 |
2024-04-13T05:44:19 Z |
riariti |
CSS (COI14_css) |
C++17 |
|
104 ms |
49328 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.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);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
32860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
33720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
49064 KB |
Output is correct |
| 2 |
Correct |
50 ms |
33112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
49060 KB |
Output is correct |
| 2 |
Correct |
47 ms |
33288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
11612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
48976 KB |
Output is correct |
| 2 |
Correct |
90 ms |
33856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
74 ms |
49088 KB |
Output is correct |
| 2 |
Correct |
60 ms |
33532 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
77 ms |
49328 KB |
Output is correct |
| 2 |
Correct |
89 ms |
33628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
104 ms |
48976 KB |
Output is correct |
| 2 |
Correct |
59 ms |
33316 KB |
Output is correct |
