답안 #90241 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
90241	2018-12-21T01:43:57 Z	jasony123123	CSS (COI14_css)	C++11	60 / 100	1155 ms	17984 KB

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
typedef string hsh;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll INF = 1e18;
#define MOD1 1000000009LL
#define MOD2 2038072819LL
#define PRI1 610639LL
#define PRI2 949957LL
/****************************************************************/

const int MAXN = 5100, MAXS = 5100;
int N = 0;
string name[MAXN];
v<hsh> classes[MAXN];
v<int> chi[MAXN];

v<pair<char, v<hsh>>> selector;
bool dp[MAXS][MAXN];
bool dpanc[MAXS][MAXN];

bool isGood(v<hsh> &clas, v<hsh> &mustHave) {
	for (auto &x : mustHave) {
		if (!binary_search(all(clas), x))
			return 0;
	}
	return 1;
}

void dfs(int s, int x, int p) {
	if (x == 0) {
		dp[s][x] = 0;
		dpanc[s][x] = 0;
	}
	else {
		if (s == 0) {
			dp[s][x] = isGood(classes[x], selector[s].second);
		}
		else {
			if (selector[s].first == ' ') {
				dp[s][x] = isGood(classes[x], selector[s].second) && dpanc[s - 1][p];
			}
			else {
				dp[s][x] = isGood(classes[x], selector[s].second) && dp[s - 1][p];
			}
		}
		dpanc[s][x] = dp[s][x] || dpanc[s][p];
	}

	for (int c : chi[x]) {
		dfs(s, c, x);
	}
}

void modd(ll &x, ll m) {
	x %= m;
}
pll calcHash(string &str) {
	pll ret = { 0,0 };
	pll p = { 1,1 };
	for (char c : str) {
		modd(ret.first += c*p.first, MOD1);
		modd(ret.second += c*p.second, MOD2);
		modd(p.first *= PRI1, MOD1);
		modd(p.second *= PRI2, MOD2);
	}
	return ret;
}
v<string> split(string &str) {
	v<string> ret;
	string word = "";
	for (auto c : str) {
		if (c == ' ') {
			if (word != "") {
				ret.push_back(word);
				word = "";
			}
		}
		else if (c == '\n') {
			break;
		}
		else {
			word += c;
		}
	}
	ret.push_back(word);
	return ret;
}
void parse(string &line, int idx) { // fill name + classes
	v<int> pos;
	pos.push_back(line.find('\''));
	pos.push_back(line.find('\'', pos.back() + 1));
	pos.push_back(line.find('\'', pos.back() + 1));
	pos.push_back(line.find('\'', pos.back() + 1));
	
	name[idx] = line.substr(pos[0] + 1, pos[1] - pos[0] + 1 - 2);
	line = line.substr(pos[2] + 1, pos[3] - pos[2] + 1 - 2);
	v<string> clist = split(line);
	classes[idx] = clist;
	sort(all(classes[idx]));
}
void init() {
	int lines;
	cin >> lines;
	stack<int> stac;
	stac.push(N++);
	cin.ignore();

	FOR(i, 0, lines) {
		string lin;
		getline(cin, lin);
		if (lin[1] == '/')
			stac.pop();
		else {
			parse(lin, N);
			chi[stac.top()].push_back(N);
			stac.push(N++);
		}
	}
}
void checkparse() {
	dvar(N);
	darr(name, N);
	FOR(i, 0, N) {
		cout << i << ": ";
		for (auto &x : classes[i])
			cout << x << ", ";
		cout << "\n";
	}
	FOR(i, 0, N) {
		cout << i << ": ";
		for (auto &x : chi[i])
			cout << x << ", ";
		cout << "\n";
	}
}

void parseSelector(string &str) {
	v<string> ss;
	ss = split(str);
	selector.clear();
	selector.push_back({ '6', v<hsh>() });
	
	for (string &token : ss) {
		if (token[0] == '.') {
			replace(all(token), '.', ' ');
			selector.back().second = split(token);
			selector.push_back({ ' ', v<hsh>() });
		}
		else {
			selector.back().first = token[0];
		}
	}
	selector.pop_back();
}
void checkSelector() {
	for (auto x : selector) {
		cout << x.first << "\n";
		for (auto s : x.second)
			cout << s << ", ";
		cout << "\n\n";
	}
}

int main() {
	io();
	init();
//	checkparse();
	
	int M;
	cin >> M;
	cin.ignore();

	FOR(i, 0, M) {
		string line;
		getline(cin, line);
		parseSelector(line);
	//	checkSelector();
		FOR(s, 0, selector.size())
			dfs(s, 0, -1);
		v<string> ans;

		FOR(x, 1, N)
			if (dp[selector.size() - 1][x])
				ans.push_back(name[x]);
		
		cout << ans.size() << " ";
		for (auto x : ans)
			cout << x << " ";
		cout << "\n";
	}
	return 0;
}

Subtask #1
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	760 KB	Output isn't correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	1840 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	5 ms	1840 KB	Output isn't correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	142 ms	12716 KB	Output is correct
2	Correct	636 ms	12716 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	176 ms	12716 KB	Output is correct
2	Correct	663 ms	12716 KB	Output is correct

Subtask #6
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	12716 KB	Output is correct

Subtask #7
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	82 ms	12716 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	89 ms	12716 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #9
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	318 ms	12716 KB	Output is correct
2	Correct	983 ms	17984 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1155 ms	17984 KB	Output is correct
2	Correct	597 ms	17984 KB	Output is correct

답안 #90241

Compilation message