| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 90243 |
2018-12-21T01:58:09 Z |
jasony123123 |
CSS (COI14_css) |
C++11 |
|
964 ms |
17320 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 << " ";
puts("");
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
760 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
1812 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1812 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
12744 KB |
Output is correct |
| 2 |
Correct |
636 ms |
12744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
171 ms |
12744 KB |
Output is correct |
| 2 |
Correct |
681 ms |
12744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
12744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
85 ms |
12744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
85 ms |
12744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
243 ms |
12744 KB |
Output is correct |
| 2 |
Correct |
964 ms |
17320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
805 ms |
17320 KB |
Output is correct |
| 2 |
Correct |
643 ms |
17320 KB |
Output is correct |
