oj.uz

Submission #1065931

# Submission time Handle Problem Language Result Execution time Memory
1065931 2024-08-19T13:14:13 Z vjudge1 CSS (COI14_css) C++17
100 / 100
 1487 ms 8652 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], dout[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){
			dout[x] = tree_nodes;
			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;
			int pnt = 0;
			for(auto &i : v){
				pnt = max(pnt, (int)(upper_bound(r.begin(), r.end(), i) - r.begin()));
				while(pnt < r.size() && r[pnt] <= dout[i]){
					ans.push_back(r[pnt++]);
				}
			}
			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 of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   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::string)':
css.cpp:92:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for(int i=0; i<s.size(); ){
      |               ~^~~~~~~~~
css.cpp:94:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   while(nxt < s.size() && s[nxt] != '.') nxt++;
      |         ~~~~^~~~~~~~~~
css.cpp:104:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |  for(int i=0; i<v.size(); ){
      |               ~^~~~~~~~~
css.cpp:106:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   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:115:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for(int i=1; i<s.size(); i++){
      |               ~^~~~~~~~~
css.cpp:130:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |     while(pnt < r.size() && r[pnt] <= dout[i]){
      |           ~~~~^~~~~~~~~~
css.cpp: In function 'int main()':
css.cpp:148:12: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  148 |   printf("%d ", ret.size());
      |           ~^    ~~~~~~~~~~
      |            |            |
      |            int          std::vector<int>::size_type {aka long unsigned int}
      |           %ld
css.cpp: In function 'std::vector<std::__cxx11::basic_string<char> > readline_split()':
css.cpp:9:7: warning: ignoring return value of 'char* fgets(char*, int, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  fgets(buf, 5005, stdin);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
css.cpp: In function 'int main()':
css.cpp:141:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |  scanf("%d\n",&n);
      |  ~~~~~^~~~~~~~~~~
css.cpp:144:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |  scanf("%d\n", &m);
      |  ~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2908 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3164 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1487 ms 3596 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8580 KB Output is correct
2 Correct 578 ms 3412 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 8536 KB Output is correct
2 Correct 545 ms 3560 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2908 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 8536 KB Output is correct
2 Correct 822 ms 3412 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 8600 KB Output is correct
2 Correct 471 ms 3412 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 8532 KB Output is correct
2 Correct 795 ms 3412 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 8652 KB Output is correct
2 Correct 480 ms 3412 KB Output is correct