답안 #105203

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
105203	2019-04-11T00:03:11 Z	Shtef	CSS (COI14_css)	C++14	10 / 100	5000 ms	61432 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], curidx = 0;
stack <int> st;
vector <int> tr;
vector <vector <int> > b;
string imena[5005];
vector <bool> znak;
bool bio[5][5005][5005], dp[5][5005][5005], ima[5005][10005];

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

bool dfs(int x, int sad, bool type){
	if(sad == -1)
		return 1;
	if(!x)
		return 0;
	if(bio[curidx][x][sad] != bio[curidx][x][sad])
		return dp[curidx][x][sad];
	bio[curidx][x][sad] = 1;
	dp[curidx][x][sad] = 0;
	if(type){
		if(svesadrzi(x, b[sad])){
			dp[curidx][x][sad] |= dfs(par[x], sad - 1, znak[sad]);
		}
	}
	else{
		if(svesadrzi(x, b[sad])){
			dp[curidx][x][sad] |= dfs(par[x], sad - 1, znak[sad]);
		}
		dp[curidx][x][sad] |= dfs(par[x], sad, type);
	}
	return dp[curidx][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();
	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:32:25: warning: self-comparison always evaluates to false [-Wtautological-compare]
  if(bio[curidx][x][sad] != bio[curidx][x][sad])
     ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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