oj.uz

답안 #105194

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
105194 2019-04-10T23:47:40 Z Shtef CSS (COI14_css) C++14
20 / 100
 5000 ms 263168 KB 
#include <iostream>
#include <map>
#include <string>
#include <stack>
#include <vector>
#include <cstring>

using namespace std;

map <string, int> oznake;
int n, m, idx = 1, koji = 1, par[10005];
stack <int> st;
vector <int> tr;
vector <vector <int> > b;
map <int, bool> ima[10005], bio[10005], dp[10005];
string imena[10005];
vector <bool> znak;

bool svesadrzi(int x, vector <int> &v){
	for(int i = 0 ; i < (int)v.size() ; ++i){
		if(ima[x].find(v[i]) == ima[x].end())
			return 0;
	}
	return 1;
}

bool dfs(int x, int sad, bool type){
	if(sad == -1)
		return 1;
	if(!x)
		return 0;
	if(bio[x].find(sad) != bio[x].end())
		return dp[x][sad];
	bio[x][sad] = 1;
	dp[x][sad] = 0;
	if(type){
		if(svesadrzi(x, b[sad])){
			dp[x][sad] |= dfs(par[x], sad - 1, znak[sad]);
		}
	}
	else{
		if(svesadrzi(x, b[sad])){
			dp[x][sad] |= dfs(par[x], sad - 1, znak[sad]);
		}
		dp[x][sad] |= dfs(par[x], sad, type);
	}
	return dp[x][sad];
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 0 ; i < n ; ++i){
	string s;
	cin >> s;
	if(s == "</div>"){
		st.pop();
		continue;
	}
	cin >> s;
	for(int j = 4 ; j < (int)s.size() && s[j] >= 'a' && s[j] <= 'z' ; ++j){
		imena[koji] += s[j];
	}
	if(!st.empty()){
		par[koji] = st.top();
	}
	else{
		tr.push_back(koji);
	}
	st.push(koji);
	koji++;
	cin >> s;
	string t = "";
	for(int j = 7 ; j < (int)s.size() && s[j] >= 'a' && s[j] <= 'z' ; ++j){
		t += s[j];
	}
	if(oznake.find(t) == oznake.end()){
		oznake[t] = idx;
		idx++;
	}
	ima[koji - 1][oznake[t]] = 1;
	bool p = ((s[(int)s.size() - 1] == '>') ^ 1);
	while(p){
		cin >> s;
		if(s[(int)s.size() - 1] == '>'){
			p = 0;
			s = s.substr(0, (int)s.size() - 2);
		}
		if(oznake.find(s) == oznake.end()){
			oznake[s] = idx;
			idx++;
		}
		ima[koji - 1][oznake[s]] = 1;
	}
}
/*
for(int i = 1 ; i < koji ; ++i){
	cout << par[i] << ' ';
}
cout << endl;
*/
cin >> m;
cin.ignore();
for(int i = 0 ; i < m ; ++i){
	string s;
	getline(cin, s);
	string sad = "";
	bool p = 0;
	znak.push_back(0);
	vector <int> v;
	for(int j = 1 ; j < (int)s.size() ; ++j){
		if(s[j] >= 'a' && s[j] <= 'z'){
			sad += s[j];
		}
		else if(s[j] == '>'){
			p = 1;
		}
		else if(s[j] == '.'){
			if(s[j - 1] == ' '){
				v.push_back(oznake[sad]);
				b.push_back(v);
				znak.push_back(p);
				v.clear();
				sad.clear();
				p = 0;
			}
			else{
				v.push_back(oznake[sad]);
				sad.clear();
			}
		}
	}
	v.push_back(oznake[sad]);
	b.push_back(v);
	/*
	for(int j = 0 ; j < (int)b.size() ; ++j){
		cout << znak[j] << ' ';
	}
	cout << endl;
	*/
	vector <int> ans;
	for(int j = 1 ; j < koji ; ++j){
		if(dfs(j, (int)b.size() - 1, 1)){
			ans.push_back(j);
		}
	}
	cout << (int)ans.size() << " ";
	for(int j = 0 ; j < (int)ans.size() ; ++j){
		cout << imena[ans[j]] << " ";
	}
	cout << endl;
	b.clear();
	znak.clear();
	for(int j = 1 ; j < koji ; ++j){
		bio[j].clear();
		dp[j].clear();
	}
}

return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 2304 KB Output isn't correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 5248 KB Output is correct

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5078 ms 226200 KB Time limit exceeded

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 203 ms 23736 KB Output is correct
2 Execution timed out 5051 ms 207028 KB Time limit exceeded

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 235 ms 25648 KB Output is correct
2 Execution timed out 5090 ms 254644 KB Time limit exceeded

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2304 KB Output is correct

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 206 ms 23292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 277 ms 26716 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 310 ms 28792 KB Output is correct
2 Runtime error 4081 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1250 ms 53568 KB Output is correct
2 Execution timed out 5080 ms 263168 KB Time limit exceeded