Submission #1115847

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1115847	2024-11-21T02:44:07 Z	vjudge1	CSS (COI14_css)	C++14	100 / 100	179 ms	7248 KB

#include<bits/stdc++.h>
using namespace std;

const int N = 5005, M = 5e6 + 5;

map<string, int> M1;
map<string, int> M2;
int tot1, tot2;

int get_name_id(string &s){
	if(M1.count(s))return M1[s];
	return M1[s] = ++ tot1;
}

int get_cls_id(string s){
	if(M2.count(s))return M2[s];
	return M2[s] = ++ tot2;
}

struct Node{
	string name;
	vector<int> cls;
}w[N];
int cnt;


int fa[N];
vector<int> e[N];

bitset<N> f[N];
// bool f[N][N];
vector<int> que[N];
vector<string> ans;
int szq;
int tp[N];

bool check_in(vector<int> &b, vector<int> &a){
	static bool st[M] = {};
	for(int u : b)st[u] = 1;
	bool flg = 1;
	for(int u : a)flg &= st[u];
	for(int u : b)st[u] = 0;

	return flg;
}

void dfs(int x){
	if(f[fa[x]][szq - 1] && check_in(w[x].cls, que[szq])){
		ans.push_back(w[x].name);
	}

	f[x][0] = 1;
	for(int i = 1; i <= szq; i ++){
		if(tp[i] == 0 && f[fa[x]][i])f[x][i] = 1;
		else if(f[fa[x]][i - 1] && check_in(w[x].cls, que[i]))f[x][i] = 1;
	}

	for(int u : e[x])dfs(u);
}



char ss[N * 2], ch;
vector<int> rts;

int main(){

	int n;
	scanf("%d", &n);

	int idnow = 0;
	for(int i = 1; i <= n; i ++){
		scanf(" <%c", &ch);
		if(ch == '/')idnow = fa[idnow], scanf("div>");
		else {
			scanf("iv id='%s'", ss); 
			ss[strlen(ss) - 1] = '\00';

			fa[++ cnt] = idnow;
			idnow = cnt;
			w[idnow].name = ss;

			scanf(" class = \'%s", ss);
			bool flg = 1;
			while(flg){
				int len = strlen(ss);
				if(ss[len - 1] == '>')ss[len - 2] = '\00', flg = 0;
				string s2 = ss;
				w[idnow].cls.push_back(get_cls_id(s2));
				if(flg)scanf("%s", ss);
			}
		}
	}

	for(int i = 1; i <= cnt; i ++){
		if(fa[i] == 0)rts.push_back(i);
		else e[fa[i]].push_back(i);
	}

	int m;
	scanf("%d", &m);

	string s;
	getline(cin, s);
	for(int TT = 1; TT <= m; TT ++){
		stringstream SS;
		getline(cin, s);
		SS << s;

		int tot = 0;

		memset(tp, 0, sizeof(tp));
		while(SS >> s){
			if(s == ">")tp[tot] = 1;
			else {
				tot ++;
				que[tot].clear();
				int pos = 1;
				while(pos < (int)s.size()){
					auto t = s.find(".", pos);
					if(t == string::npos)t = s.size();
					que[tot].push_back(get_cls_id(s.substr(pos, t - pos)));
					pos = t + 1;
				}
			}
		}

		ans.clear();
		szq = tot;
		for(int i = 0; i <= cnt; i ++)f[i].reset();
		// memset(f, 0, sizeof(f));
		f[0][0] = 1;

		for(int u : rts)dfs(u);

		cout << ans.size() << " ";
		for(auto u : ans)cout << u << " "; 
		cout << '\n';
	}
}

Compilation message

css.cpp: In function 'int main()':
css.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
css.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   scanf(" <%c", &ch);
      |   ~~~~~^~~~~~~~~~~~~
css.cpp:74:40: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   if(ch == '/')idnow = fa[idnow], scanf("div>");
      |                                   ~~~~~^~~~~~~~
css.cpp:76:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |    scanf("iv id='%s'", ss);
      |    ~~~~~^~~~~~~~~~~~~~~~~~
css.cpp:83:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |    scanf(" class = \'%s", ss);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~
css.cpp:90:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     if(flg)scanf("%s", ss);
      |            ~~~~~^~~~~~~~~~
css.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |  scanf("%d", &m);
      |  ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4688 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	5200 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	54 ms	5712 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	7244 KB	Output is correct
2	Correct	39 ms	5448 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	7240 KB	Output is correct
2	Correct	39 ms	5448 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	4688 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	7248 KB	Output is correct
2	Correct	64 ms	5624 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	90 ms	6992 KB	Output is correct
2	Correct	47 ms	5456 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	92 ms	7240 KB	Output is correct
2	Correct	62 ms	5648 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	179 ms	7164 KB	Output is correct
2	Correct	43 ms	5456 KB	Output is correct