201809-3 元素选择器

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 const int N = 2000 + 5;
  6 
  7 struct elem{
  8     string tag;
  9     string id;
 10     int fa;
 11 };
 12 
 13 vector<elem> elem(105);
 14 vector<int> ans;
 15 int n, m;
 16 int get_subs(string str, string sub[50]) {
 17     istringstream in(str);
 18     int idx = 0;
 19     while(in >> sub[idx]) idx++;
 20     return idx;
 21 }
 22 
 23 int check_ancestor(string sub[50], int items, int fa) {
 24     while(items > 0) {
 25         string p;
 26 
 27         if(fa == -1)
 28             return 0;
 29         if(sub[items - 1][0] == '#')
 30             p = elem[fa].id;
 31         else
 32             p = elem[fa].tag;
 33 
 34         if(sub[items - 1] == p)
 35             items --;
 36         fa = elem[fa].fa;
 37     }
 38     return 1;
 39 }
 40 void query(string str) {
 41     int i, id = 0, s_cnt;
 42     string sub[50];
 43 
 44     s_cnt = get_subs(str, sub);
 45     for(i = 0; i < s_cnt; i++)
 46         if(sub[i][0] != '#')
 47              transform(sub[i].begin(), sub[i].end(), sub[i].begin(), ::toupper);
 48 
 49     string& s = sub[s_cnt - 1];
 50     if(s[0] == '#')
 51         id = 1;
 52 
 53     ans.clear();
 54     for(i = 0; i < n; i++) {
 55         string p;
 56         if(id)
 57             p = elem[i].id;
 58         else
 59             p = elem[i].tag;
 60         if(p == s)
 61             if(check_ancestor(sub, s_cnt - 1, elem[i].fa))
 62                 ans.push_back(i + 1);
 63     }
 64 }
 65 
 66 void print_result() {
 67     cout << ans.size() ;
 68     for(size_t i = 0; i < ans.size(); i++) {
 69         cout << " " << ans[i];
 70     }
 71     cout << endl;
 72 }
 73 
 74 int main() {
 75 
 76     string str;
 77     int level[101] = {-1};
 78     cin >> n >> m;
 79     getchar();
 80     for(int i = 0; i < n; i++) {
 81         int c;
 82         getline(cin, str);
 83         c = count(str.begin(), str.end(), '.');
 84         level[c / 2] = i;
 85 
 86         elem[i].id.clear();
 87         istringstream s(str.substr(c));
 88         if(s >> elem[i].tag) s >> elem[i].id;
 89         if(i)
 90             elem[i].fa = level[c / 2 - 1];
 91         transform(elem[i].tag.begin(), elem[i].tag.end(), elem[i].tag.begin(), ::toupper);
 92     }
 93     elem[0].fa = -1;
 94 
 95     for(int i = 0; i < m; i++) {
 96         getline(cin, str);
 97         query(str);
 98         print_result();
 99     }
100     return 0;
101 }