Submission #105384

#TimeUsernameProblemLanguageResultExecution timeMemory
105384ShtefCSS (COI14_css)C++14
60 / 100
2943 ms212760 KiB
#include <iostream> #include <cstdio> #include <set> #include <stack> #include <string> #include <cstring> #include <vector> #include <algorithm> using namespace std; typedef long long ll; const ll mod = (ll)1e9 + 7; const ll B = 100003LL; ll h(char *s){ ll ret = 0; for(char *c = s ; *c ; ++c){ ret = ((ret * B) % mod + *c - 'a' + 1) % mod; } return ret; } struct node{ string ime; set <ll> klase; vector <int> ms; node() {} node(char *s): ime(s) {} void staviklasu(char *s){ klase.insert(h(s)); } void dodajchild(int x){ ms.push_back(x); } }; struct query{ vector <vector <ll> > koji; vector <int> znak; void dodajelement(vector <ll> v){ koji.push_back(v); } void dodajznak(int x){ znak.push_back(x); } }; int n, m, dp[2][5005][5005], idx; stack <int> st; vector <node> t; query g[15]; vector <int> ans; bool provjeri(node &x, vector <ll> &v){ if(x.klase.empty()) return 0; for(vector <ll>::iterator i = v.begin() ; i != v.end() ; ++i){ ll o = *i; if(x.klase.find(o) == x.klase.end()) return 0; } return 1; } void dfs(int x, int sad, bool je){ int &ret = dp[je][x][sad]; if(ret != -1) return; ret = 0; if(sad >= (int)g[idx].znak.size()){ ret = (je ^ 1); if(ret){ ans.push_back(x); } return; } if(g[idx].znak[sad] == 0){ if(je){ dfs(x, sad + 1, 0); } for(vector <int>::iterator i = t[x].ms.begin() ; i != t[x].ms.end() ; ++i){ int o = *i; dfs(o, sad, 1); } } else if(g[idx].znak[sad] == 1){ for(vector <int>::iterator i = t[x].ms.begin() ; i != t[x].ms.end() ; ++i){ int o = *i; dfs(o, sad + 1, 0); } } else{ if(!provjeri(t[x], g[idx].koji[sad / 2])) return; dfs(x, sad + 1, 0); } } int main(){ scanf("%d", &n); st.push(0); t.push_back(node()); for(int i = 0 ; i < n ; ++i){ char s[25]; scanf("%s", s); if(!strcmp(s, "</div>")){ st.pop(); continue; } scanf(" id='%[^']'", s); t.push_back(node(s)); t[st.top()].dodajchild((int)t.size() - 1); st.push((int)t.size() - 1); scanf(" class='"); while(scanf(" %[^ ']", s)){ t.back().staviklasu(s); } scanf("'>"); } scanf("%d\n", &m); for(int i = 0 ; i < m ; ++i){ char s[25]; bool p = 0; int sad = 0; vector <ll> v; g[i].dodajznak(0); g[i].dodajznak(2); scanf("."); while(1){ scanf("%[^. \n]", s); char c; scanf("%c", &c); if(c == '\n') break; if(c == '.'){ v.push_back(h(s)); continue; } scanf("%c", &c); if(c == '>'){ p = 1; scanf(" ."); } v.push_back(h(s)); g[i].dodajelement(v); g[i].dodajznak(p); g[i].dodajznak(2); v.clear(); p = 0; } v.push_back(h(s)); g[i].dodajelement(v); /* for(int j = 0 ; j < (int)g[i].znak.size() ; ++j){ cout << g[i].znak[j] << ": "; } cout << endl; */ v.clear(); memset(dp, -1, sizeof(dp)); dfs(0, 0, 0); sort(ans.begin(), ans.end()); printf("%d ", (int)ans.size()); for(int j = 0 ; j < (int)ans.size() ; ++j){ printf("%s", t[ans[j]].ime.c_str()); if(j < (int)ans.size() - 1){ printf(" "); } } printf("\n"); ans.clear(); idx++; } return 0; }

Compilation message (stderr)

css.cpp: In function 'int main()':
css.cpp:126:6: warning: unused variable 'sad' [-Wunused-variable]
  int sad = 0;
      ^~~
css.cpp:102:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d", &n);
 ~~~~~^~~~~~~~~~
css.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", s);
  ~~~~~^~~~~~~~~
css.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" id='%[^']'", s);
  ~~~~~^~~~~~~~~~~~~~~~~~
css.cpp:116:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" class='");
  ~~~~~^~~~~~~~~~~~
css.cpp:120:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("'>");
  ~~~~~^~~~~~
css.cpp:122:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d\n", &m);
 ~~~~~^~~~~~~~~~~~
css.cpp:130:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(".");
  ~~~~~^~~~~
css.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%[^. \n]", s);
   ~~~~~^~~~~~~~~~~~~~~
css.cpp:134:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c", &c);
   ~~~~~^~~~~~~~~~
css.cpp:141:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%c", &c);
   ~~~~~^~~~~~~~~~
css.cpp:144:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" .");
    ~~~~~^~~~~~
#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...