Submission #1115834

# Submission time Handle Problem Language Result Execution time Memory
1115834 2024-11-21T02:21:59 Z vjudge1 CSS (COI14_css) C++17
100 / 100
287 ms 44360 KB
#include<bits/stdc++.h>
using namespace std;
const int N=5010;
int fa[N],nw;char buf[30],tmp[30];
string name[N];int ntot,mtot;
map<string,int>dict;int tot;
int fd(const string& tmp){
    if(!dict[tmp])dict[tmp]=++tot;
    return dict[tmp];
}
unordered_set<int>cls[N];
bool chkt[N][N],lnk[N];
char f[N][N];vector<int>son[N];
void dfs(int x) {
    for(int i=0;i<=mtot;i++)
        if(f[fa[x]][i])f[x][i]=1;
    for(int i=1;i<=mtot;i++){
        if(!chkt[i][x])continue;
        if(f[fa[x]][i-1]==2)f[x][i]=2;
        else if(f[fa[x]][i-1]==1&&!lnk[i-1])f[x][i]=2;
    }
    for(auto &y:son[x]) dfs(y);
}
void cl(string c,int id){
    int buf,x=0,y;vector<int>res;
    while(x<c.length()){
        y=c.find('.',x+1);
        res.push_back(fd(c.substr(x+1,y-x-1)));
        x=y;
    }
    for(int i=1;i<=ntot;i++){
        bool f=0;
        for(auto j:res)if(!cls[i].count(j)){f=1;break;}
        chkt[id][i]=!f;
    }
}
int n,m;
int main(){
    scanf("%d",&n);
    while(n--){
        scanf("%s",buf);
        if(buf[1]=='/')nw=fa[nw];
        else {
            scanf("%s",buf);sscanf(buf,"id='%[^']'",tmp);
            name[++ntot]=tmp;fa[ntot]=nw;
            son[nw].push_back(ntot);nw=ntot;
            scanf(" class='%[^ ']",tmp);cls[nw].insert(fd(tmp));
            while(1){
                if(!scanf("%*[ ]%[^ ']",tmp))break;
                cls[nw].insert(fd(tmp));
            }
        }
        scanf("%*[^\n]\n");
    }
    // for(int i=1;i<=ntot;i++){
    //     cerr<<"fa:"<<fa[i]<<",i:"<<i<<endl;
    //     cerr<<"name:"<<name[i]<<",class:";
    //     for(auto x:cls[i])cerr<<x<<" ";cerr<<endl;
    // }
    scanf("%d",&m);
    while(m--){
        scanf("%s",tmp);int num=0;cl(tmp,++num);
        while(1){
            lnk[num]=0;if(!scanf("%*[ ]%[^ \r\n]",tmp))break;
            if(tmp[0]=='>')lnk[num]=1,scanf("%s",tmp);
            cl(tmp,++num);
        }
        scanf("%*[^\n]\n"),mtot=num;
        // for(int i=1;i<=num;i++){
        //     for(int j=1;j<=ntot;j++)cerr<<chkt[i][j];cerr<<endl;
        //     cerr<<lnk[i]<<endl;
        // }
        // cerr<<endl;
        memset(f,0,sizeof f),f[0][0]=1,dfs(0);
        vector<int>ans;
        for(int i=1;i<=ntot;i++)if(f[i][num]==2)ans.push_back(i);
        printf("%d",(int)ans.size());
        for(auto &i: ans)printf(" %s",name[i].c_str());puts("");
    }
    return 0;
}

Compilation message

css.cpp: In function 'void cl(std::string, int)':
css.cpp:26:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     while(x<c.length()){
      |           ~^~~~~~~~~~~
css.cpp:25:9: warning: unused variable 'buf' [-Wunused-variable]
   25 |     int buf,x=0,y;vector<int>res;
      |         ^~~
css.cpp: In function 'int main()':
css.cpp:78:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   78 |         for(auto &i: ans)printf(" %s",name[i].c_str());puts("");
      |         ^~~
css.cpp:78:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   78 |         for(auto &i: ans)printf(" %s",name[i].c_str());puts("");
      |                                                        ^~~~
css.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
css.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%s",buf);
      |         ~~~~~^~~~~~~~~~
css.cpp:44:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |             scanf("%s",buf);sscanf(buf,"id='%[^']'",tmp);
      |             ~~~~~^~~~~~~~~~
css.cpp:47:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |             scanf(" class='%[^ ']",tmp);cls[nw].insert(fd(tmp));
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~
css.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%*[^\n]\n");
      |         ~~~~~^~~~~~~~~~~~~
css.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |     scanf("%d",&m);
      |     ~~~~~^~~~~~~~~
css.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf("%s",tmp);int num=0;cl(tmp,++num);
      |         ~~~~~^~~~~~~~~~
css.cpp:65:44: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |             if(tmp[0]=='>')lnk[num]=1,scanf("%s",tmp);
      |                                       ~~~~~^~~~~~~~~~
css.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         scanf("%*[^\n]\n"),mtot=num;
      |         ~~~~~^~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 9 ms 27472 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 17 ms 28496 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 212 ms 36936 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 127 ms 42204 KB Output is correct
2 Correct 160 ms 34640 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 133 ms 42308 KB Output is correct
2 Correct 159 ms 34632 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 7 ms 27640 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 125 ms 42312 KB Output is correct
2 Correct 237 ms 36936 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 150 ms 44360 KB Output is correct
2 Correct 145 ms 34632 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 160 ms 44360 KB Output is correct
2 Correct 213 ms 36892 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 287 ms 44360 KB Output is correct
2 Correct 162 ms 34632 KB Output is correct