oj.uz

Submission #464960

# Submission time Handle Problem Language Result Execution time Memory
464960 2021-08-14T15:45:10 Z BERNARB01 CSS (COI14_css) C++17
10 / 100
 1538 ms 202288 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 5003;

int par[N];
string id[N];
bool bl[N][N], dp[N][N], vis[N][N];
set<string> clss[N];
vector<string> clf[N];

bool sol(int i, int j) {
	if (j == -1) return true;
	if (i == -1) return false;
	if (vis[i][j]) return dp[i][j];
	vis[i][j] = true;
	dp[i][j] = sol(par[i], j);
	if (bl[i][j]) dp[i][j] |= sol(par[i], j - 1);
	return dp[i][j];
}

bool ok(int i, int j) {
	for (auto x : clf[j]) {
		if (clss[i].find(x) == clss[i].end()) return false;
	}
	return true;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> stk(1, -1);
	int idd = -1;
	for (int i = 0; i < n; i++) {
		string div;
		cin >> div;
		if (div == "</div>") {
			stk.pop_back();
		} else {
			++idd;
			par[idd] = stk.back();
			stk.push_back(idd);
			cin >> id[idd];
			id[idd] = id[idd].substr(4, id[idd].length() - 5);
			string C;
			getline(cin >> ws, C);
			stringstream ss(C);
			while (ss >> C) {
				if (C.length() > 5 && C[5] == '=') {
					C = C.substr(7, C.length() - 7);
				}
				if (C.back() == '>') {
					C.pop_back();
					C.pop_back();
				}
				clss[idd].insert(C);
			}
		}
	}
	idd++;
	int m;
	cin >> m;
	while (m--) {
		memset(dp, false, sizeof dp);
		memset(bl, 0, sizeof bl);
		memset(vis, 0, sizeof vis);
		for (int i = 0; i < N; i++) {
			clf[i].clear();
		}
		string k;
		getline(cin >> ws, k);
		stringstream ss(k);
		int j = 0;
		while (ss >> k) {
			if (k.length() == 1) {
				assert(false);
			}
			for (char c : k) {
				if (c == '.') {
					clf[j].emplace_back();
				} else {
					clf[j].back() += c;
				}
			}
			j++;
		}
		for (int i = 0; i < idd; i++) {
			for (int jj = 0; jj < j; jj++) {
				bl[i][jj] = ok(i, jj);
			}
		}
		vector<string> res;
		for (int i = 0; i < idd; i++) {
			if (sol(i, j - 1)) {
				res.emplace_back(id[i]);
			}
		}
		cout << res.size();
		for (int i = 0; i < (int) res.size(); i++) {
			cout << " " << res[i];
		}
		cout << '\n';
	}
	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 74380 KB Output isn't correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 93 ms 75488 KB Output isn't correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1538 ms 75464 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 258 ms 100488 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 273 ms 100408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 104 ms 150472 KB Execution killed with signal 6

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 232 ms 202244 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 238 ms 202288 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 243 ms 202152 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 234 ms 202164 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -