Submission #1115820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115820		vjudge1	CSS (COI14_css)	C++14	100 / 100	237 ms	106324 KiB

css

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<string>

#define fi first
#define se second
#define mkp std::make_pair
using ll=long long;
using std::min;
using std::max;
template<class T> void cmax(T&a,T b){a=max(a,b);}
template<class T> void cmin(T&a,T b){a=min(a,b);}

namespace xm{
    std::map<std::string,int> clmp;
    std::vector<std::string> clname;
    std::vector<int> bel[5005],G[5005];
    int N,stk[5005],vcnt,ccnt;
    char buf[405],qbuf[5005],cbuf[5005],id[5005][21];

    std::vector<std::pair<bool,std::vector<int> > > restrict;
    std::vector<int> ans;
    int dfn[5005],dfr[5005],dfc,subtim,vis[2000000],able[5005][5005];
    void dfs(int x){
        dfn[x]=++dfc;
        for(int t:G[x]) dfs(t);
        dfr[x]=dfc;
    }bool issub(std::vector<int>&a,std::vector<int>&b){
        ++subtim;
        for(int x:a) vis[x]=subtim;
        for(int y:b) if(vis[y]!=subtim) return 0;
        return 1;
    }void dfscmp(int x){
        if(x) for(int i=0;i<(int)restrict.size();++i)
            if(able[x][i]&&issub(bel[x],restrict[i].se)){
                //printf("%d %d\n",x,i);
                if(i==(int)restrict.size()-1) ans.push_back(x);
                if(i!=(int)restrict.size()-1&&restrict[i+1].fi){
                    for(int t:G[x]) able[t][i+1]=1;
                }else{
                    for(int t:G[x]) ++able[t][i+1];
                }
            }
        if(x) for(int t:G[x]){
            for(int i=0;i<(int)restrict.size();++i)
                if(!restrict[i].fi) able[t][i]+=able[x][i];
        }
        for(int t:G[x]){
            dfscmp(t);
        }
    }

    void _(){
        scanf("%d",&N);
        clname.push_back("");
        for(int i=1;i<=N;++i){
            scanf("%s",buf);
            if(buf[1]=='/'){
                --*stk;
            }else{
                stk[++*stk]=++vcnt;
                scanf("%s",buf);
                buf[strlen(buf)-1]='\0';
                strcpy(id[vcnt],buf+4);
                for(bool F=1;;){
                    scanf("%s",buf);
                    bool breakf=0;
                    int le=strlen(buf);
                    if(buf[le-1]=='>'){
                        buf[le-2]=0;
                        le-=2;
                        breakf=1;
                    }
                    std::string classname=F?buf+7:buf;
                    if(clmp.find(classname)==clmp.end()){
                        clmp[classname]=++ccnt;
                        clname.push_back(classname);
                    }
                    bel[vcnt].push_back(clmp[classname]);
                    if(breakf) break;
                    F=0;
                }
                std::sort(bel[vcnt].begin(),bel[vcnt].end());
                G[*stk==1?0:stk[*stk-1]].push_back(vcnt);
            }
        }
        //for(int i=1;i<=N/2;++i) puts(id[i]);
        //for(int i=1;i<=N/2;++i){
        //    for(int x:bel[i]) printf("%s ",clname[x].c_str());
        //    puts("");
        //}
        //for(int i=0;i<=N/2;++i){
        //    for(int t:G[i]) printf("%d %d\n",i,t);
        //}

        int Q;
        scanf("%d\n",&Q);
        while(Q--){
            fgets(qbuf,sizeof qbuf,stdin);
            restrict.clear();
            ans.clear();
            bool reF=0;
            for(int cur=0;;){
                int thisdelta,ret;
                if((ret=sscanf(qbuf+cur," %s%n",cbuf,&thisdelta))!=1){
                    break;
                }
                cur+=thisdelta;
                if(cbuf[0]=='>'){
                    reF=1;
                    continue;
                }
                std::vector<int> pat;
                for(int i=1;;){
                    int j=i,cn=0;
                    for(;cbuf[j]!='.'&&cbuf[j]!='\0';++j) buf[cn++]=cbuf[j];
                    buf[cn]='\0';
                    pat.push_back(clmp[std::string(buf)]);
                    if(cbuf[j]=='\0') break;
                    i=j+1;
                }
                restrict.emplace_back(reF,pat);
                reF=0;
            }
            //for(auto p:restrict){
            //    printf("%d ",p.fi);
            //    for(int x:p.se) printf("%s ",clname[x].c_str());
            //    puts("");
            //}
            memset(able,0,sizeof able);
            for(int i=0;i<=N/2;++i) able[i][0]=1;
            dfscmp(0);
            printf("%zu",ans.size());
            for(int x:ans) printf(" %s",id[x]);
            puts("");
        }
    }
}

int main(){
    xm::_();
    return 0;
}

Compilation message (stderr)

css.cpp: In function 'void xm::_()':
css.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d",&N);
      |         ~~~~~^~~~~~~~~
css.cpp:60:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |             scanf("%s",buf);
      |             ~~~~~^~~~~~~~~~
css.cpp:65:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |                 scanf("%s",buf);
      |                 ~~~~~^~~~~~~~~~
css.cpp:69:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |                     scanf("%s",buf);
      |                     ~~~~~^~~~~~~~~~
css.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         scanf("%d\n",&Q);
      |         ~~~~~^~~~~~~~~~~
css.cpp:102:18: warning: ignoring return value of 'char* fgets(char*, int, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |             fgets(qbuf,sizeof qbuf,stdin);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• 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