| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 105198 |
2019-04-10T23:54:19 Z |
Shtef |
CSS (COI14_css) |
C++14 |
|
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])
~~~~~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
361 ms |
27256 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5063 ms |
28372 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5084 ms |
45688 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5072 ms |
41216 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5067 ms |
41052 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
27384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5095 ms |
60680 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5020 ms |
60568 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5086 ms |
41384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5045 ms |
41252 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
