oj.uz

Submission #53476

# Submission time Handle Problem Language Result Execution time Memory
53476 2018-06-30T05:43:03 Z pce913 CSS (COI14_css) C++17
60 / 100
 2138 ms 89332 KB 
#include <cstdio>
#include <cstring>
#include <stack>
#include <string>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

struct HTMLelement {
	string id;
	set<int> classes;
	vector<int> children;
	HTMLelement() {}
	HTMLelement(char *name):
		id(name) {}

	void add_child(int child_id) {
		children.push_back(child_id);
	}

	void add_class(char *str) {
		int hash = 0;
		for(char *ptr = str; *ptr; ++ptr)
			hash = hash * 71 + *ptr - 'a' + 1;
		classes.insert(hash);
	}
};

struct SelectorElement {
	int type;
	vector<int> classes;
	SelectorElement(int type):
		type(type) {}

	void add_class(char *str) {
		int hash = 0;
		for(char *ptr = str; *ptr; ++ptr)
			hash = hash * 71 + *ptr - 'a' + 1;
		classes.push_back(hash);
	}

	bool check(const HTMLelement &E) {
		for(auto cls : classes)
			if(E.classes.find(cls) == E.classes.end())
				return 0;
		return 1;
	}
};

vector<HTMLelement> read_document(void) {
	int N; scanf("%d", &N);

	stack<int> ancestors;

	vector<HTMLelement> tree;
	tree.push_back(HTMLelement());
	ancestors.push(0);

	for(int i = 0; i < N; ++i) {
		char tag_start[11];
		scanf("%s", tag_start);
		if(strcmp(tag_start, "</div>") == 0) {
			ancestors.pop();
		} else {
			char name[31];
			scanf(" id='%[^']'", name);

			tree.push_back(HTMLelement(name));
			tree[ancestors.top()].add_child(tree.size() - 1);
			ancestors.push(tree.size() - 1);

			scanf(" class='");
			char class_name[31];
			while(scanf(" %[^ ']", class_name))
				tree.back().add_class(class_name);
			scanf("'>");
		}
	}

	return tree;
}

vector<SelectorElement> read_selector(void) {
	vector<SelectorElement> sel;

	char c;
	while(scanf("%c", &c)) {
		if(c == ' ') continue;
		if(c == '\n') break;
		if(c == '>') {
			sel.push_back(SelectorElement(0));
			scanf(" %c", &c);
		} else
			sel.push_back(SelectorElement(1));
	
		sel.push_back(SelectorElement(2));

		char class_name[21];
		while(scanf("%[^. \n]", class_name)) {
			sel.back().add_class(class_name);
			scanf(".");
		}
	}

	return sel;
}

vector<HTMLelement> DocumentTree;
vector<SelectorElement> Selector;
bool visited[2][5010][5010];

void dfs(int jump, int node, int pos, vector<int> &ans) {
	if(visited[jump][node][pos]) return;
	visited[jump][node][pos] = 1;

	if(pos == Selector.size()) {
		if(!jump) ans.push_back(node);
		return;
	}

	if(Selector[pos].type == 0) {
		for(auto child : DocumentTree[node].children)
			dfs(0, child, pos + 1, ans);
	}

	if(Selector[pos].type == 1) {
		if(jump) dfs(0, node, pos + 1, ans);
		for(auto child : DocumentTree[node].children)
			dfs(1, child, pos, ans);
	}

	if(Selector[pos].type == 2) {
		if(!Selector[pos].check(DocumentTree[node])) return;
		dfs(0, node, pos + 1, ans);
	}
}

int main(void) {
	
	DocumentTree = read_document();

	int M; scanf("%d\n", &M);
	for(int i = 0; i < M; ++i) {
		Selector = read_selector();

		memset(visited, 0, sizeof visited);
		vector<int> ans;

		dfs(0, 0, 0, ans);

		printf("%d ", (int)ans.size());
		sort(ans.begin(), ans.end());
		for(auto id : ans) printf("%s ", DocumentTree[id].id.c_str());
		printf("\n");
	}

	return 0;

}

Compilation message

css.cpp: In function 'void dfs(int, int, int, std::vector<int>&)':
css.cpp:118:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(pos == Selector.size()) {
     ~~~~^~~~~~~~~~~~~~~~~~
css.cpp: In function 'std::vector<HTMLelement> read_document()':
css.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N; scanf("%d", &N);
         ~~~~~^~~~~~~~~~
css.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", tag_start);
   ~~~~~^~~~~~~~~~~~~~~~~
css.cpp:68:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" id='%[^']'", name);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~
css.cpp:74:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" class='");
    ~~~~~^~~~~~~~~~~~
css.cpp:78:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("'>");
    ~~~~~^~~~~~
css.cpp: In function 'std::vector<SelectorElement> read_selector()':
css.cpp:94:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c", &c);
    ~~~~~^~~~~~~~~~~
css.cpp:103:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(".");
    ~~~~~^~~~~
css.cpp: In function 'int main()':
css.cpp:144:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int M; scanf("%d\n", &M);
         ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 49528 KB Output isn't correct

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2138 ms 52188 KB Output isn't correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 69928 KB Output is correct
2 Correct 1111 ms 69928 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 74060 KB Output is correct
2 Correct 1142 ms 74060 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 279 ms 77832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 387 ms 81516 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 622 ms 85388 KB Output is correct
2 Correct 1754 ms 85388 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1538 ms 89332 KB Output is correct
2 Correct 1131 ms 89332 KB Output is correct