# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
53478 | pce913 | CSS (COI14_css) | C++17 | 146 ms | 34876 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<set>
#include<unordered_map>
#include<algorithm>
using namespace std;
char in[5005];
unordered_map<string, int> mp1, mp2;
string its[10005]; //몇번 아이디를 가지고 있는 녀석의 실제 글자.
int GN1, GN2;
vector<int> a[10005];
set<int> cls[10005];
int parent[10005];
vector<int> v[5005];
bool mode[5005]; //1: 부모-자식관계 노드만 찾기 ,0: 그외
int d;
vector<int> ans;
int get_id(string t){
if (mp1.count(t))return mp1[t];
return mp1[t] = ++GN1;
}
int get_class(string t){
if (mp2.count(t))return mp2[t];
return mp2[t] = ++GN2;
}
void dfs(int node,int depth){
bool choose = 1;
for (int i = 0; i < v[depth].size(); i++){
if (!cls[node].count(v[depth][i])){
choose = 0;
break;
}
}
int ndepth = depth;
if (choose)
ndepth++;
if (depth == d - 1 && choose){
ans.push_back(node);
if (ans.size() == 4500){
int aa = 3;
}
for (int i = 0; i < a[node].size(); i++){
int next = a[node][i];
dfs(next, depth);
}
}
else if (!mode[depth] || (mode[depth] && choose)){
for (int i = 0; i < a[node].size(); i++){
int next = a[node][i];
dfs(next, ndepth);
}
}
}
int main(){
//freopen("input.txt", "r", stdin);
//freopen("output.txt","w",stdout);
int n;
scanf("%d ", &n);
int cur = 0;
for (int qq = 0; qq < n; qq++){
fgets(in, 5001, stdin);
string s = in;
s.pop_back();
if (s.size() > 6){
string t = "";
int i = 9;
for (;s[i]!='\''; i++)
t.push_back(s[i]);
if (t == "tdiulonlyn"){
int aa = 3;
}
int nid = get_id(t);
a[cur].push_back(nid);
parent[nid] = cur;
its[nid] = t;
int b = s.find('\'', i + 1);
for (int i = b+1;; i++){
if (s[i] == ' ' || s[i] == '\''){
int nc = get_class(s.substr(b+1, i - b - 1));
cls[nid].insert(nc);
b = i;
if (s[i] == '\'')break;
}
}
cur = nid;
}
else cur = parent[cur];
}
int m;
scanf("%d ",&m);
for (int qq = 0; qq < m; qq++){
d = 0;
ans.clear();
memset(mode, 0, sizeof(mode));
fgets(in, 5001, stdin);
string s = in;
if (s.back()=='\n'){
s.pop_back();
}
s.push_back(' ');
int j = 0;
while (j < s.size()){
v[d].clear();
int k = s.find(' ', j);
string t = "";
for (int i = j + 1; i <= k; i++){
if (s[i] == '.' || i == k){
v[d].push_back(get_class(t));
t = "";
}
else t.push_back(s[i]);
}
if (s[k + 1] == '>'){
mode[d + 1] = 1;
j = k + 3;
}
else j = k + 1; //다음 .으로 설정하기
d++;
}
dfs(0, 0);
sort(ans.begin(), ans.end());
printf("%d ", ans.size());
int i = 0;
for (; i < (int)ans.size()-1; i++){
printf("%s ", its[ans[i]].c_str());
}
printf("%s\n", its[ans[i]].c_str());
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |