Submission #1337509

#TimeUsernameProblemLanguageResultExecution timeMemory
1337509NikoBaoticCSS (COI14_css)C++20
0 / 100
258 ms327680 KiB
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define F first
#define S second
#define FIO ios_base::sync_with_stdio(false); cin.tie(0)
#define sz(x) ((int)((x).size()))
#define all(x) x.begin(), x.end()
#define pb push_back
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e4 + 10;
const int Q = 7;
const int L = 5e3 + 10;
const int MOD1 = 1e9 + 7;
const int B1 = 31337;
const int MAX = 5e6 + 10;

int n;
string f[N];
int q;
string qu[Q];
map<ll, int> conv;
vector<string> back;
int compCnt = 1;
int name[N];
vector<int> cl[N];
int par[N];
vector<int> chi[N];
int sel[L];
bool dir[L];
vector<int> con[L];
int dp[N][L][2];
int mem[N][L];
bool ap[MAX];

int compress(string& x) {
	ll h1 = 0;

	for (char c : x) {
		h1 = ((h1 * B1 % MOD1) + (c - 'a')) % MOD1;
	}

	int val = conv[h1];

	if (val == 0) {
		val = compCnt++;
		conv[h1] = val;
		back.pb(x);
	}

	return val;
}

string readUntil(string& data, int pos, char stop = '-') {
	string cur;

	while (pos < sz(data) and data[pos] != ' ' and data[pos] != '\'' and data[pos] != stop) {
		cur.pb(data[pos]);
		pos++;
	}

	return cur;
}

bool match(int line, int pos) {
	if (mem[line][pos] != -1) return mem[line][pos];

	for (int x : cl[line]) {
		ap[x] = 1;
	}

	bool ans = 1;

	for (int x : con[pos]) {
		if (!ap[x]) ans = 0;
	}

	for (int x : cl[line]) {
		ap[x] = 0;
	}

	mem[line][pos] = ans;
	return ans;
}

bool can(int line, int pos, bool h) {
	if (pos < 0) return 1;
	if (line <= 0) return 0;
	if (dp[line][pos][h] != -1) return dp[line][pos][h];

	bool ans = 0;

	if (h) {
		ans = match(line, pos) and (can(par[line], pos - 1, dir[pos]) or can(par[line], pos - 1, 1));
	} else {
		ans = can(par[line], pos, 0) or can(par[line], pos, 1);	
	}

	dp[line][pos][h] = ans;
	return dp[line][pos][h];
}

int main() {
	FIO;

	back.pb(".");

	cin >> n;
	
	getline(cin, f[0]);

	for (int i = 1; i <= n; i++) {
		getline(cin, f[i]);
	}

	cin >> q;

	getline(cin, qu[0]);

	for (int i = 0; i < q; i++) {
		getline(cin, qu[i]);
	}

	stack<int> st;

	st.push(0);

	for (int i = 1; i <= n; i++) {
		if (f[i] == "</div>") {
			st.pop();
		} else {
			par[i] = st.top();
			chi[st.top()].pb(i);

			string nm = readUntil(f[i], 9);

			name[i] = compress(nm);

			int cur = 18 + sz(nm);

			while (f[i][cur] != '\'') {
				if (f[i][cur] == ' ') cur++;

				string x = readUntil(f[i], cur);

				cl[i].pb(compress(x));

				cur += sz(x);
			}

			st.push(i);
		}
	}

	for (int i = 0; i < q; i++) {
		for (int j = 0; j < L; j++) {
			sel[j] = 0;
			dir[j] = 0;
			con[j].clear();
		}
		memset(dp, -1, sizeof dp);
		memset(mem, -1, sizeof mem);

		int cur = 0;
		int pos = 0;

		while (cur < sz(qu[i])) {
			string sl = readUntil(qu[i], cur);

			if (sl == ">") {
				dir[pos] = 1;
			} else {
				sel[pos] = compress(sl);

				int ind = 1;

				while (ind < sz(sl)) {
					string cla = readUntil(sl, ind, '.');
					ind += sz(cla) + 1;
					con[pos].pb(compress(cla));
				}

				pos++;
			}
			
			cur += sz(sl) + 1;
		}

		vector<string> ans;

		for (int j = 1; j <= n; j++) {
			if (name[j] and can(j, pos - 1, 1)) ans.pb(back[name[j]]);
		}

		cout << sz(ans) << " ";
		for (string x : ans) {
			cout << x << " ";
		}
		cout << endl;
	}

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...