Submission #1175468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175468		Dan4Life	CSS (COI14_css)	C++20	100 / 100	1338 ms	158296 KiB

css

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ll = long long;
using vi = vector<int>;
using ar2 = array<int,2>;
const int mxN = (int)1e4+10;
const ll LINF = (ll)1e17;
int n, m;

vi adj[mxN];
map<string, int> M;
set<string> cl[mxN];
string id[mxN];
bitset<mxN> T;
int dp[mxN][1667][2];
vector<string> words, realwords;
int par[mxN];
vector<string> classes[1667];

void decompose(string s, int ind){
	classes[ind].clear();
	for(int i = 0; i < sz(s); i++){
		if(s[i]=='.') continue;
		string word = "";
		while(i<sz(s) and s[i]!='.') word+=s[i],i++;
		if(word!="") classes[ind].pb(word);
	}
}

bool corresponds(int id, int _){
	for(auto c : classes[_])
		if(!cl[id].count(c)) return 0;
	return 1;
}

bool dfs(int s, int i, int t){
	if(!s) return 0; int p = par[s];
	if(!i) { 
		int ans = corresponds(s,i);
		if(t) return corresponds(s,i);
		return corresponds(s,i) or dfs(p,i,0); 
	}
	if(dp[s][i][t]!=-1) return dp[s][i][t];
	if(!t) return dp[s][i][0] = (dfs(s,i,1) or dfs(p,i,0));
	return dp[s][i][1] = (corresponds(s,i) and dfs(p,i-1,T[i]));
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n; int ind = 1; stack<int> S;
	for(int i = 0; i < n; i++){
		string a, b, c; cin >> a;
		if(a!="</div>"){
			cin >> b; b = b.substr(4);
			b = b.substr(0,sz(b)-1);
			
			if(!M[b]) M[b] = ++ind;
			id[ind] = b;
			if(sz(S)) adj[S.top()].pb(ind), par[ind]=S.top();
			S.push(ind);
			string c="";
			bool ok = 1,stopp=0;
			while(!stopp){
				cin >> c;
				if(ok) c = c.substr(7),ok=0;
				if(c.back()=='>'){
					c = c.substr(0,sz(c)-2);
					stopp=1;
				}
				cl[ind].insert(c);
			}
		}
		else S.pop();
	}
	int q; cin >> q; cin.ignore(); 
	while(q--){
		string s; getline(cin,s);
		words.clear(); realwords.clear();
		memset(dp,-1,sizeof(dp)); T.reset();
		for(int i = 0; i < sz(s); i++){
			if(s[i]==' ') continue;
			string word = "";
			while(i<sz(s) and s[i]!=' ') word+=s[i],i++;
			if(word!="") words.pb(word);
		}
		for(auto u : words){
			if(u!=">") realwords.pb(u);
			else T[sz(realwords)]=1;
		}
		words.swap(realwords);
		vector<int> ans; ans.clear();
		for(int i = 0; i < sz(words); i++) decompose(words[i],i);
		for(int i = 1; i <= ind; i++)
			if(dfs(i,sz(words)-1,1)) ans.pb(i);
		cout << sz(ans) << " ";
		for(auto u : ans) cout << id[u] << " "; cout << "\n";
	}
}

• 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