| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 105194 |
2019-04-10T23:47:40 Z |
Shtef |
CSS (COI14_css) |
C++14 |
|
5000 ms |
263168 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[10005];
stack <int> st;
vector <int> tr;
vector <vector <int> > b;
map <int, bool> ima[10005], bio[10005], dp[10005];
string imena[10005];
vector <bool> znak;
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].find(sad) != bio[x].end())
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);
string sad = "";
bool p = 0;
znak.push_back(0);
vector <int> v;
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] == ' '){
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();
}
}
}
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;
b.clear();
znak.clear();
for(int j = 1 ; j < koji ; ++j){
bio[j].clear();
dp[j].clear();
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2304 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
5248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5078 ms |
226200 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
203 ms |
23736 KB |
Output is correct |
| 2 |
Execution timed out |
5051 ms |
207028 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
235 ms |
25648 KB |
Output is correct |
| 2 |
Execution timed out |
5090 ms |
254644 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
206 ms |
23292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
277 ms |
26716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
310 ms |
28792 KB |
Output is correct |
| 2 |
Runtime error |
4081 ms |
263168 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1250 ms |
53568 KB |
Output is correct |
| 2 |
Execution timed out |
5080 ms |
263168 KB |
Time limit exceeded |
