oj.uz

Submission #105381

# Submission time Handle Problem Language Result Execution time Memory
105381 2019-04-11T16:29:27 Z Shtef CSS (COI14_css) C++14
60 / 100
 3107 ms 212760 KB 
#include <iostream>
#include <cstdio>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
const ll mod = (ll)1e9 + 7;
const ll B = 100003LL;

ll h(char *s){
	ll ret = 0;
	for(char *c = s ; *c ; ++c){
		ret = ((ret * B) % mod + *c - 'a' + 1) % mod;
	}
	return ret;
}

struct node{
	string ime;
	set <ll> klase;
	vector <int> ms;
	node() {}
	node(char *s):
		ime(s) {}
	void staviklasu(char *s){
		klase.insert(h(s));
	}
	void dodajchild(int x){
		ms.push_back(x);
	}
};

struct query{
	vector <vector <ll> > koji;
	vector <int> znak;
	void dodajelement(vector <ll> v){
		koji.push_back(v);
	}
	void dodajznak(int x){
		znak.push_back(x);
	}
};

int n, m, dp[2][5005][5005], idx;
stack <int> st;
vector <node> t;
query g[15];
vector <int> ans;

bool provjeri(node &x, vector <ll> &v){
	if(x.klase.empty())
		return 0;
	for(vector <ll>::iterator i = v.begin() ; i != v.end() ; ++i){
		ll o = *i;
		if(x.klase.find(o) == x.klase.end())
			return 0;
	}
	return 1;
}

void dfs(int x, int sad, bool je){
	int &ret = dp[je][x][sad];
	if(ret != -1)
		return;
	ret = 0;
	if(sad >= (int)g[idx].znak.size()){
		ret = 1;
		ans.push_back(x);
		return;
	}
	if(g[idx].znak[sad] == 0){
		if(je){
			dfs(x, sad + 1, 0);
		}
		for(vector <int>::iterator i = t[x].ms.begin() ; i != t[x].ms.end() ; ++i){
			int o = *i;
			dfs(o, sad, 1);
		}
	}
	else if(g[idx].znak[sad] == 1){
		for(vector <int>::iterator i = t[x].ms.begin() ; i != t[x].ms.end() ; ++i){
			int o = *i;
			dfs(o, sad + 1, 0);
		}
	}
	else{
		if(!provjeri(t[x], g[idx].koji[sad / 2]))
			return;
		dfs(x, sad + 1, 0);
	}
}

int main(){
scanf("%d", &n);
st.push(0);
t.push_back(node());
for(int i = 0 ; i < n ; ++i){
	char s[25];
	scanf("%s", s);
	if(!strcmp(s, "</div>")){
		st.pop();
		continue;
	}
	scanf(" id='%[^']'", s);
	t.push_back(node(s));
	t[st.top()].dodajchild((int)t.size() - 1);
	st.push((int)t.size() - 1);
	scanf(" class='");
	while(scanf(" %[^ ']", s)){
		t.back().staviklasu(s);
	}
	scanf("'>");
}
scanf("%d\n", &m);
for(int i = 0 ; i < m ; ++i){
	char s[25];
	bool p = 0;
	int sad = 0;
	vector <ll> v;
	g[i].dodajznak(0);
	g[i].dodajznak(2);
	scanf(".");
	while(1){
		scanf("%[^. \n]", s);
		char c;
		scanf("%c", &c);
		if(c == '\n')
			break;
		if(c == '.'){
			v.push_back(h(s));
			continue;
		}
		scanf("%c", &c);
		if(c == '>'){
			p = 1;
			scanf(" .");
		}
		v.push_back(h(s));
		g[i].dodajelement(v);
		g[i].dodajznak(p);
		g[i].dodajznak(2);
		v.clear();
		p = 0;
	}
	v.push_back(h(s));
	g[i].dodajelement(v);
	/*
	for(int j = 0 ; j < (int)g[i].znak.size() ; ++j){
		cout << g[i].znak[j] << ": ";
	}
	cout << endl;
	*/
	v.clear();
	memset(dp, -1, sizeof(dp));
	dfs(0, 0, 0);
	sort(ans.begin(), ans.end());
	printf("%d ", (int)ans.size());
	for(int j = 0 ; j < (int)ans.size() ; ++j){
		printf("%s ", t[ans[j]].ime.c_str());
	}
	printf("\n");
	ans.clear();
	idx++;
}

return 0;
}

Compilation message

css.cpp: In function 'int main()':
css.cpp:124:6: warning: unused variable 'sad' [-Wunused-variable]
  int sad = 0;
      ^~~
css.cpp:100:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d", &n);
 ~~~~~^~~~~~~~~~
css.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", s);
  ~~~~~^~~~~~~~~
css.cpp:110:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" id='%[^']'", s);
  ~~~~~^~~~~~~~~~~~~~~~~~
css.cpp:114:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" class='");
  ~~~~~^~~~~~~~~~~~
css.cpp:118:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("'>");
  ~~~~~^~~~~~
css.cpp:120:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d\n", &m);
 ~~~~~^~~~~~~~~~~~
css.cpp:128:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(".");
  ~~~~~^~~~~
css.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%[^. \n]", s);
   ~~~~~^~~~~~~~~~~~~~~
css.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c", &c);
   ~~~~~^~~~~~~~~~
css.cpp:139:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c", &c);
   ~~~~~^~~~~~~~~~
css.cpp:142:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" .");
    ~~~~~^~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 197680 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 622 ms 212628 KB Output is correct
2 Correct 1710 ms 198064 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 668 ms 212612 KB Output is correct
2 Correct 1821 ms 198144 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 196628 KB Output is correct

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 848 ms 212564 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 972 ms 212652 KB Output is correct
2 Correct 2449 ms 198400 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2375 ms 212760 KB Output is correct
2 Correct 1663 ms 197952 KB Output is correct