| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1115819 |
2024-11-21T01:55:45 Z |
vjudge1 |
CSS (COI14_css) |
C++14 |
|
5000 ms |
100164 KB |
#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(){
freopen("css.in","r",stdin);
freopen("css.out","w",stdout);
xm::_();
return 0;
}
Compilation message
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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
css.cpp: In function 'int main()':
css.cpp:144:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
144 | freopen("css.in","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
css.cpp:145:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
145 | freopen("css.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5063 ms |
100160 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5039 ms |
100152 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5038 ms |
100156 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5049 ms |
100152 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5050 ms |
100160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5038 ms |
100164 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5042 ms |
99920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5057 ms |
99920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5026 ms |
99920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5040 ms |
99920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
