Submission #105198

#TimeUsernameProblemLanguageResultExecution timeMemory
105198ShtefCSS (COI14_css)C++14
10 / 100
5095 ms60680 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...