oj.uz

Submission #105379

# Submission time Handle Problem Language Result Execution time Memory
105379 2019-04-11T16:08:07 Z Shtef CSS (COI14_css) C++14
60 / 100
 1108 ms 118092 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;
	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

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.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 99508 KB Output is correct

Subtask #3
0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 117936 KB Output is correct
2 Correct 637 ms 99884 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 118060 KB Output is correct
2 Correct 614 ms 99808 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 98532 KB Output is correct

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 342 ms 117988 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 401 ms 117936 KB Output is correct
2 Correct 1108 ms 99936 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 118092 KB Output is correct
2 Correct 591 ms 99808 KB Output is correct