| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 476445 |
2021-09-27T03:22:14 Z |
HKLee416 |
CSS (COI14_css) |
C |
|
113 ms |
247368 KB |
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#pragma warning(disable:4996)
#define PTRSIZ 8
int hasch(char* schnur) {
unsigned int erg = 0;
for (char* zei = schnur; *zei; zei++)
erg = (erg * 0x47 + *zei - 0x60) % 4294967295;
return (int)erg;
}
typedef struct vektor {
void** daten;
int gross;
} Vektor;
Vektor* schaffen_vektor() {
Vektor* erg = (Vektor*)malloc(sizeof(Vektor));
erg->daten = (void**)malloc(0);
erg->gross = 0;
return erg;
}
void anfugen_vektor(Vektor* v, void* daten) {
v->daten = (void**)realloc(v->daten, PTRSIZ * (v->gross + 1));
v->daten[v->gross] = daten;
v->gross++;
}
int vektor_hat(Vektor* v, void* ziel) {
for (int i = 0; i < v->gross; i++)
if (v->daten[i] == ziel) return 1;
return 0;
}
void frei_alledaten(Vektor* v) {
for (int i = 0; i < v->gross; i++)
free(v->daten[i]);
free(v->daten);
free(v);
return;
}
typedef struct stapel {
void** daten;
int niveau;
} Stapel;
Stapel* schaffen_stapel() {
Stapel* erg = (Stapel*)malloc(sizeof(Stapel));
erg->daten = (void**)malloc(0);
erg->niveau = 0;
return erg;
}
void anfugen_stapel(Stapel* s, void* daten) {
s->daten = (void**)realloc(s->daten, PTRSIZ * (s->niveau + 1));
s->daten[s->niveau] = daten;
s->niveau++;
}
void* pop_stapel(Stapel* s) {
s->niveau--;
void* erg = s->daten[s->niveau];
s->daten = (void**)realloc(s->daten, PTRSIZ * (s->niveau));
return erg;
}
typedef struct HTMLElement {
char* id;
Vektor* klassen;
Vektor* kinder;
} Node;
Node* schaffen_nodeN() {
Node* erg = (Node*)malloc(sizeof(Node));
erg->id = (char*)0;
erg->klassen = schaffen_vektor();
erg->kinder = schaffen_vektor();
return erg;
}
Node* schaffen_node(char* id) {
Node* erg = (Node*)malloc(sizeof(Node));
erg->id = (char*)malloc(sizeof(id));
strcpy(erg->id, id);
erg->klassen = schaffen_vektor();
erg->kinder = schaffen_vektor();
return erg;
}
void anfugen_klassen(Node* e, char* klasse) {
anfugen_vektor(e->klassen, (void*)hasch(klasse));
}
void anfugen_kind(Node* e, int kind) {
anfugen_vektor(e->kinder, (void*)kind);
}
typedef struct SelectorElement {
int typ;
Vektor* klassen;
} FilterNode;
FilterNode* schaffen_filternode(int typ) {
FilterNode* erg = (FilterNode*)malloc(sizeof(FilterNode));
erg->typ = typ;
if (typ == 2) erg->klassen = schaffen_vektor();
return erg;
}
void anfugen_klassen_filternode(FilterNode* f, char* klasse) {
anfugen_vektor(f->klassen, (void*)hasch(klasse));
}
int prufen_node(FilterNode* f, Node* n) {
for (int i = 0; i < f->klassen->gross; i++)
if (!vektor_hat(n->klassen, f->klassen->daten[i])) return 0;
return 1;
}
Vektor* dokument_lasen() {
int G; scanf("%d", &G);
Stapel* vorfahren = schaffen_stapel();
Vektor* erg = schaffen_vektor();
anfugen_vektor(erg, schaffen_nodeN());
anfugen_stapel(vorfahren, 0);
for (int i = 0; i < G; i++) {
char schildsanfang[11];
scanf("%s", schildsanfang);
if (!strcmp(schildsanfang, "</div>")) pop_stapel(vorfahren);
else {
char name[31];
scanf(" id='%[^']'", name);
anfugen_vektor(erg, schaffen_node(name));
anfugen_kind((Node*)erg->daten[(int)vorfahren->daten[vorfahren->niveau - 1]], erg->gross - 1);
anfugen_stapel(vorfahren, (void*)(erg->gross - 1));
scanf(" class='");
char klasse_name[31];
while (scanf(" %[^ ']", klasse_name)) anfugen_klassen((Node*)erg->daten[erg->gross - 1], klasse_name);
scanf("'>");
}
}
return erg;
}
Vektor* wahler_lasen() {
Vektor* erg = schaffen_vektor();
char c;
while (scanf("%c", &c)) {
switch (c) {
case 0x20:
goto FORT;
case 0x0A:
goto BREC;
case 0x3E:
anfugen_vektor(erg, schaffen_filternode(0));
scanf(" %c", &c);
break;
default:
anfugen_vektor(erg, schaffen_filternode(1));
break;
}
anfugen_vektor(erg, schaffen_filternode(2));
char klasse_name[21];
while (scanf("%[^. \n]", klasse_name)) {
FilterNode* n = (FilterNode*)erg->daten[erg->gross - 1];
anfugen_klassen_filternode(n, klasse_name);
scanf(".");
}
FORT:
continue;
}
BREC:
return erg;
}
typedef struct tragen {
Vektor* wahler;
Vektor* antworten;
bool hat_besucht[2][5010][5010];
} Tragen;
Tragen* schaffen_tragen() {
Tragen* erg = (Tragen*)malloc(sizeof(Tragen));
return erg;
}
void frei_tragen(Tragen* tra) {
frei_alledaten(tra->wahler);
frei_alledaten(tra->antworten);
free(tra);
return;
}
void dfs(Tragen* tra, Vektor* dokumentenbaum, bool spr, int nod, int pos) {
if (tra->hat_besucht[spr][nod][pos]) return;
tra->hat_besucht[spr][nod][pos] = 1;
if (pos == tra->wahler->gross) {
if (!spr) anfugen_vektor(tra->antworten, (void*)nod);
return;
}
Vektor* kdr;
switch (((FilterNode*)tra->wahler->daten[pos])->typ) {
case 0:
kdr = ((Node*)dokumentenbaum->daten[nod])->kinder;
for (int i = 0; i < kdr->gross; i++)
dfs(tra, dokumentenbaum, 0, (int)kdr->daten[i], pos + 1);
break;
case 1:
if (spr) dfs(tra, dokumentenbaum, 0, nod, pos + 1);
kdr = ((Node*)dokumentenbaum->daten[nod])->kinder;
for (int i = 0; i < kdr->gross; i++)
dfs(tra, dokumentenbaum, 1, (int)kdr->daten[i], pos);
break;
case 2:
if (!prufen_node((FilterNode*)tra->wahler->daten[pos], (Node*)dokumentenbaum->daten[nod])) return;
dfs(tra, dokumentenbaum, 0, nod, pos + 1);
break;
}
}
int compare(const void* a, const void* b) {
return (*(int*)a) - (*(int*)b);
}
int main(void) {
Vektor* baum = dokument_lasen();
int G; scanf("%d\n", &G);
for (int i = 0; i < G; i++) {
Vektor* fil = wahler_lasen();
Tragen* tra = schaffen_tragen();
tra->wahler = fil;
tra->antworten = schaffen_vektor();
memset(tra->hat_besucht, 0, sizeof tra->hat_besucht);
dfs(tra, baum, 0, 0, 0);
Vektor* ant = tra->antworten;
printf("%d ", ant->gross);
qsort((int*)ant->daten, ant->gross, sizeof(int), compare);
for (int j = 0; j < ant->gross; j++)
printf("%s ", ((Node*)baum->daten[(int)ant->daten[j]])->id);
printf("\n");
//frei_tragen(tra);
}
return 0;
}
Compilation message
css.c:5: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
5 | #pragma warning(disable:4996)
|
css.c: In function 'anfugen_klassen':
css.c:100:29: warning: cast to pointer from integer of different size [-Wint-to-pointer-cast]
100 | anfugen_vektor(e->klassen, (void*)hasch(klasse));
| ^
css.c: In function 'anfugen_kind':
css.c:104:28: warning: cast to pointer from integer of different size [-Wint-to-pointer-cast]
104 | anfugen_vektor(e->kinder, (void*)kind);
| ^
css.c: In function 'anfugen_klassen_filternode':
css.c:121:29: warning: cast to pointer from integer of different size [-Wint-to-pointer-cast]
121 | anfugen_vektor(f->klassen, (void*)hasch(klasse));
| ^
css.c: In function 'dokument_lasen':
css.c:148:35: warning: cast from pointer to integer of different size [-Wpointer-to-int-cast]
148 | anfugen_kind((Node*)erg->daten[(int)vorfahren->daten[vorfahren->niveau - 1]], erg->gross - 1);
| ^
css.c:149:30: warning: cast to pointer from integer of different size [-Wint-to-pointer-cast]
149 | anfugen_stapel(vorfahren, (void*)(erg->gross - 1));
| ^
css.c: In function 'dfs':
css.c:216:44: warning: cast to pointer from integer of different size [-Wint-to-pointer-cast]
216 | if (!spr) anfugen_vektor(tra->antworten, (void*)nod);
| ^
css.c:225:32: warning: cast from pointer to integer of different size [-Wpointer-to-int-cast]
225 | dfs(tra, dokumentenbaum, 0, (int)kdr->daten[i], pos + 1);
| ^
css.c:231:32: warning: cast from pointer to integer of different size [-Wpointer-to-int-cast]
231 | dfs(tra, dokumentenbaum, 1, (int)kdr->daten[i], pos);
| ^
css.c: In function 'main':
css.c:263:38: warning: cast from pointer to integer of different size [-Wpointer-to-int-cast]
263 | printf("%s ", ((Node*)baum->daten[(int)ant->daten[j]])->id);
| ^
css.c: In function 'dokument_lasen':
css.c:132:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
132 | int G; scanf("%d", &G);
| ^~~~~~~~~~~~~~~
css.c:142:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
142 | scanf("%s", schildsanfang);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~
css.c:146:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
146 | scanf(" id='%[^']'", name);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~
css.c:150:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
150 | scanf(" class='");
| ^~~~~~~~~~~~~~~~~
css.c:153:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
153 | scanf("'>");
| ^~~~~~~~~~~
css.c: In function 'wahler_lasen':
css.c:171:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
171 | scanf(" %c", &c);
| ^~~~~~~~~~~~~~~~
css.c:182:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
182 | scanf(".");
| ^~~~~~~~~~
css.c: In function 'main':
css.c:248:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
248 | int G; scanf("%d\n", &G);
| ^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
93 ms |
246084 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
247368 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
