Submission #26933

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
26933	2017-07-07T08:15:46 Z	gs14004	CSS (COI14_css)	C++14	20 / 100	5000 ms	32048 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 && buf[n-1] == '\n') 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 && 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];
string num_to_class[100005];
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;
					num_to_class[class_count] = i;
				}
				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);
		}
	}
}

int cnt[5005] = {};
vector<int> parse_brj(string s){
	memset(cnt, 0, sizeof(cnt));
	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]){
			cnt[j]++;
		}
		i = nxt;
	}
	vector<int> v;
	for(int i=1; i<=tree_nodes; i++){
		if(cnt[i] == ok) v.push_back(i);
	}
	return v;
}

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

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:49: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:88:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<s.size(); ){
                ^
css.cpp:90:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(nxt < s.size() && s[nxt] != '.') nxt++;
             ^
css.cpp: In function 'int main()':
css.cpp:142: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:135:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d\n",&n);
                  ^
css.cpp:138:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d\n", &m);
                   ^

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	3 ms	7704 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	7988 KB	Output is correct

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	9 ms	7864 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	139 ms	9628 KB	Output is correct
2	Execution timed out	5000 ms	23860 KB	Execution timed out

Subtask #5
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	153 ms	9712 KB	Output is correct
2	Execution timed out	5000 ms	23856 KB	Execution timed out

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	7704 KB	Output is correct

Subtask #7
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	0 ms	7836 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	0 ms	7704 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	176 ms	10036 KB	Output is correct
2	Execution timed out	5000 ms	32048 KB	Execution timed out

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	726 ms	12332 KB	Output is correct
2	Execution timed out	5000 ms	23980 KB	Execution timed out