Submission #1116011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116011		vjudge1	CSS (COI14_css)	C++17	100 / 100	170 ms	37448 KiB

css

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<unordered_map>
#define ll long long
using namespace std;
const int MAXN=5e3+10;
int n,m,tot,cnt;string s;
vector <int> f[MAXN],ans;
unordered_map <string,int> Classname;
vector <pair<vector<int>,bool>> Selector;
struct Div
{
    int fa;string Name;vector <int> SonDiv;
    unordered_map <int,bool> Class;
}D[MAXN];
inline bool Check(int x,int i)
{
    for(int now:Selector[i].first)
        if(D[x].Class.find(now)==D[x].Class.end()) return false;
    return true;
}
void dfs(int x)
{
    f[x].clear();
    for(int i:f[D[x].fa])
    {
        if(f[x].empty()||f[x].back()!=i)
            if(!Selector[i].second) f[x].push_back(i);
        if(Check(x,i)) f[x].push_back(i+1);
    }
    if(!f[x].empty()&&f[x].back()==Selector.size())
        ans.push_back(x),f[x].pop_back();
    if(f[x].empty()) return ;
    for(int y:D[x].SonDiv) dfs(y);
}
signed main()
{
    cin.tie(0),cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n,f[0].push_back(0);
    for(int i=1,cur=0;i<=n;++i)
    {
        cin>>s;if(s=="</div>"){cur=D[cur].fa;continue;}
        ++tot,D[D[tot].fa=cur].SonDiv.push_back(tot);
        cin>>s,D[tot].Name=s.substr(4,s.size()-5);
        cin>>s,s.erase(0,7);
        while(bool flag=true)
        {
            if(s.back()=='>')
                flag=false,s.erase(s.size()-2,2);
            if(!Classname[s]) Classname[s]=++cnt;
            D[tot].Class[Classname[s]]=true;
            if(!flag) break;cin>>s;
        }cur=tot;
    }
    cin>>m,getline(cin,s);
    while(m--)
    {
        Selector.clear(),getline(cin,s);
        while(!islower(s.back())) s.pop_back();
        s=s+' ';bool flag=false;
        Selector.push_back({{},flag});
        for(int i=0,j=0;;i=j)
        {
            j=i+1;while(islower(s[j])) ++j;
            string now=s.substr(i+1,j-i-1);
            if(Classname.find(now)==Classname.end())
                {cout<<"0\n";goto end;}
            Selector.back().first.push_back(Classname[now]);
            if(j==s.size()-1) break;if(s[j]=='.') continue;
            if(s[j+1]=='>') flag=true,j+=3;
            else flag=false,j+=1;
            Selector.push_back({{},flag});
        }
        for(int x:D[0].SonDiv) dfs(x);
        cout<<ans.size()<<' ';
        for(int x:ans) cout<<D[x].Name<<' ';
        cout<<'\n',ans.clear();end:;
    }
    return 0;
}

Compilation message (stderr)

css.cpp: In function 'void dfs(int)':
css.cpp:34:34: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<std::pair<std::vector<int>, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     if(!f[x].empty()&&f[x].back()==Selector.size())
      |                       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~
css.cpp: In function 'int main()':
css.cpp:56:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   56 |             if(!flag) break;cin>>s;
      |             ^~
css.cpp:56:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   56 |             if(!flag) break;cin>>s;
      |                             ^~~
css.cpp:73:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             if(j==s.size()-1) break;if(s[j]=='.') continue;
      |                ~^~~~~~~~~~~~
css.cpp:73:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   73 |             if(j==s.size()-1) break;if(s[j]=='.') continue;
      |             ^~
css.cpp:73:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   73 |             if(j==s.size()-1) break;if(s[j]=='.') continue;
      |                                     ^~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10