Submission #105379

#	Time	Username	Problem	Language	Result	Execution time	Memory
105379		Shtef	CSS (COI14_css)	C++14	60 / 100	1108 ms	118092 KiB

css

#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;
	int par;
	node() {}
	node(char *s):
		ime(s) {}
	void staviklasu(char *s){
		klase.insert(h(s));
	}
	void dodajparent(int x){
		par = 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[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;
}

int dfs(int x, int sad){
	if(sad == -1)
		return 1;
	if(!x)
		return 0;
	int &ret = dp[x][sad];
	if(ret != -1)
		return ret;
	ret = 0;
	if(g[idx].znak[sad]){
		if(provjeri(t[x], g[idx].koji[sad])){
			ret = dfs(t[x].par, sad - 1);
		}
	}
	else{
		if(provjeri(t[x], g[idx].koji[sad])){
			ret = dfs(t[x].par, sad - 1);
		}
		ret |= dfs(t[x].par, sad);
	}
	return ret;
}

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[(int)t.size() - 1].dodajparent(st.top());
	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;
	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);
	g[i].dodajznak(1);
	/*
	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));
	for(int j = 1 ; j < (int)t.size() ; ++j){
		if(dfs(j, (int)g[i].koji.size() - 1)){
			ans.push_back(j);
		}
	}
	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 (stderr)

css.cpp: In function 'int main()':
css.cpp:115:6: warning: unused variable 'sad' [-Wunused-variable]
  int sad = 0;
      ^~~
css.cpp:91:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d", &n);
 ~~~~~^~~~~~~~~~
css.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", s);
  ~~~~~^~~~~~~~~
css.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" id='%[^']'", s);
  ~~~~~^~~~~~~~~~~~~~~~~~
css.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" class='");
  ~~~~~^~~~~~~~~~~~
css.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("'>");
  ~~~~~^~~~~~
css.cpp:111:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d\n", &m);
 ~~~~~^~~~~~~~~~~~
css.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(".");
  ~~~~~^~~~~
css.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%[^. \n]", s);
   ~~~~~^~~~~~~~~~~~~~~
css.cpp:121:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c", &c);
   ~~~~~^~~~~~~~~~
css.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c", &c);
   ~~~~~^~~~~~~~~~
css.cpp:131:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" .");
    ~~~~~^~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 0 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10