oj.uz

Submission #26953

# Submission time Handle Problem Language Result Execution time Memory
26953 2017-07-07T12:09:04 Z gs14004 CSS (COI14_css) C++14
30 / 100
 5000 ms 6528 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;

char buf[5005];

vector<string> readline_split(){
	fgets(buf, 5005, stdin);
	int n = strlen(buf);
	while(n > 0 && (isspace(buf[n-1]) || !isprint(buf[n-1]))) n--;
	buf[n] = 0;
	vector<string> ret;
	string cur;
	for(int i=0; i<n; i++){
		if(buf[i] == ' '){
			if(!cur.empty()) ret.push_back(cur);
			cur.clear();
		}
		else cur.push_back(buf[i]);
	}
	if(!cur.empty()) ret.push_back(cur);
	return ret;
}

struct docline{
	int is_end;
	string name;
	vector<string> classes;
};

int n;

docline read_docline(){
	n--;
	auto l = readline_split();
	docline ret;
	if(l.size() == 1){
		assert(l[0] == "</div>");
		ret.is_end = 1;
		return ret;
	}
	ret.is_end = 0;
	ret.name = l[1].substr(4, l[1].size() - 5);
	if(l.size() == 3){
		ret.classes.push_back(l[2].substr(7, l[2].size() - 9));
	}
	else{
		ret.classes.push_back(l[2].substr(7, l[2].size() - 7));
		for(int i=3; i+1<l.size(); i++) ret.classes.push_back(l[i]);
		ret.classes.push_back(l.back().substr(0, l.back().size() - 2));
	}
	return ret;
}

map<string, int> class_to_num;
string num_to_name[5005];
vector<int> class_node[100005];
int tree_nodes, class_count, par[5005];

void make_tree(){
	stack<int> stk;
	stk.push(0);
	while(n && !stk.empty()){
		int x = stk.top();
		docline in = read_docline();
		if(in.is_end == 1) stk.pop();
		else{
			tree_nodes++;
			for(auto &i : in.classes){
				if(class_to_num.find(i) == class_to_num.end()){
					class_to_num[i] = ++class_count;
				}
				class_node[class_to_num[i]].push_back(tree_nodes);
			}
			par[tree_nodes] = x;
			num_to_name[tree_nodes] = in.name;
			stk.push(tree_nodes);
		}
	}
	assert(class_count <= 100000);
	assert(tree_nodes <= 5000);
	assert(n == 0);
}

vector<int> parse_brj(string s){
	vector<int> v;
	int ok = 0;
	for(int i=0; i<s.size(); ){
		int nxt = i+1;
		while(nxt < s.size() && s[nxt] != '.') nxt++;
		int x = class_to_num[s.substr(i + 1, nxt - i - 1)];
		ok++;
		for(auto &j : class_node[x]){
			v.push_back(j);
		}
		i = nxt;
	}
	sort(v.begin(), v.end());
	vector<int> ans;
	for(int i=0; i<v.size(); ){
		int e = i;
		while(e < v.size() && v[e] == v[i]) e++;
		if(e - i == ok) ans.push_back(v[i]);
		i = e;
	}
	return ans;
}

vector<int> query(vector<string> &s){
	auto v = parse_brj(s[0]);
	for(int i=1; i<s.size(); i++){
		if(s[i] == ">"){
			auto r = parse_brj(s[++i]);
			vector<int> ans;
			for(auto &i : r){
				if(binary_search(v.begin(), v.end(), par[i])) ans.push_back(i);
			}
			v = ans;
		}
		else{
			auto r = parse_brj(s[i]);
			vector<int> ans;
			for(auto &i : r){
				for(int j=par[i]; j; j=par[j]){
					if(binary_search(v.begin(), v.end(), j)){
						ans.push_back(i);
						break;
					}
				}
			}
			v = ans;
		}
	}
	return v;
}

int main(){
	scanf("%d\n",&n);
	make_tree();
	int m;
	scanf("%d\n", &m);
	while(m--){
		auto in = readline_split();
		auto ret = query(in);
		printf("%d ", ret.size());
		for(auto &i : ret){
			printf("%s ", num_to_name[i].c_str());
		}
		puts("");
	}
}

Compilation message

css.cpp: In function 'docline read_docline()':
css.cpp:50:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=3; i+1<l.size(); i++) ret.classes.push_back(l[i]);
                   ^
css.cpp: In function 'std::vector<int> parse_brj(std::__cxx11::string)':
css.cpp:89:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<s.size(); ){
                ^
css.cpp:91:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(nxt < s.size() && s[nxt] != '.') nxt++;
             ^
css.cpp:101:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); ){
                ^
css.cpp:103:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(e < v.size() && v[e] == v[i]) e++;
           ^
css.cpp: In function 'std::vector<int> query(std::vector<std::__cxx11::basic_string<char> >&)':
css.cpp:112:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<s.size(); i++){
                ^
css.cpp: In function 'int main()':
css.cpp:146:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
   printf("%d ", ret.size());
                           ^
css.cpp: In function 'std::vector<std::__cxx11::basic_string<char> > readline_split()':
css.cpp:9:25: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  fgets(buf, 5005, stdin);
                         ^
css.cpp: In function 'int main()':
css.cpp:139:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d\n",&n);
                  ^
css.cpp:142:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d\n", &m);
                   ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5000 ms 4860 KB Execution timed out

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 6504 KB Output is correct
2 Execution timed out 5000 ms 4704 KB Execution timed out

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 6524 KB Output is correct
2 Execution timed out 5000 ms 4704 KB Execution timed out

Subtask #6
10.0 / 10.0

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

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 6524 KB Output is correct
2 Execution timed out 5000 ms 4704 KB Execution timed out

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 6504 KB Output is correct
2 Execution timed out 5000 ms 4696 KB Execution timed out

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 6528 KB Output is correct
2 Execution timed out 5000 ms 4704 KB Execution timed out

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 923 ms 6484 KB Output is correct
2 Execution timed out 5000 ms 4704 KB Execution timed out