답안 #105198

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
105198	2019-04-10T23:54:19 Z	Shtef	CSS (COI14_css)	C++14	10 / 100	5000 ms	60680 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[5005];
stack <int> st;
vector <int> tr;
vector <vector <int> > b;
map <int, bool> ima[5005];
string imena[5005];
vector <bool> znak;
bool bio[5005][5005], dp[5005][5005];

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][sad] != bio[x][sad])
		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);
	b.clear();
	znak.clear();
	memset(bio, 0, sizeof(bio));
	string sad = "";
	bool p = 0;
	znak.push_back(0);
	vector <int> v;
	bool f = 1;
	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] == ' '){
				if(oznake.find(sad) == oznake.end()){
					f = 0;
					break;
				}
				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();
			}
		}
	}
	if(!f){
		cout << 0 << endl;
		continue;
	}
	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;
}

return 0;
}

Compilation message

css.cpp: In function 'bool dfs(int, int, bool)':
css.cpp:33:17: warning: self-comparison always evaluates to false [-Wtautological-compare]
  if(bio[x][sad] != bio[x][sad])
     ~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5072 ms	41216 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5067 ms	41052 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6
10.0 / 10.0

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

Subtask #7
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5095 ms	60680 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5020 ms	60568 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5086 ms	41384 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5045 ms	41252 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-