Submission #921320

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define _p(...) (void)printf(__VA_ARGS__)
#define forr(x,arr) for(auto&& x:arr)
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) _rep3(i,0,n)
#define _rep3(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2,)(__VA_ARGS__)
#define _rrep2(i,n) _rrep3(i,0,n)
#define _rrep3(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2,)(__VA_ARGS__)
#define ALL(x) (x).begin(), (x).end()
#define BIT(n) (1LL<<(n))
#define SZ(x) ((int)(x).size())
#define fst first
#define snd second
using ll=long long;using pii=pair<int,int>;using vb=vector<bool>;
using vi=vector<int>;using vvi=vector<vi>;using vvvi=vector<vvi>;
using vl=vector<ll>;using vvl=vector<vl>;using vvvl=vector<vvl>;
using vd=vector<double>;using vvd=vector<vd>;using vvvd=vector<vvd>;
using vpii=vector<pii>;using vvpii=vector<vpii>;using vvvpii=vector<vvpii>;
int i() { int i; scanf("%d", &i); return i;}
int l() { ll l; scanf("%lld", &l); return l;}
vi ia(int n) {vi ret(n); rep(i, n) scanf("%d", &ret[i]); return ret;}
vl la(int n) {vl ret(n); rep(i, n) scanf("%lld", &ret[i]); return ret;}

template <typename V> struct Trie {
  const int EMPTY = -1;
  vector<vector<int>> trie;
  vector<V> vals;
  vi num_c;
  vi len;
  vb end;

  Trie() {
    assign_new_state();
  }

  void add_word(const string& word, const V& val) {
    int now = 0;
    for (char c : word) {
      c -= 'a';
      if (trie[now][c] == EMPTY) {
        trie[now][c] = SZ(trie);
        assign_new_state();
        num_c[now]++;
      }
      now = trie[now][c];
    }
    vals[now] = val;
    end[now] = 1;
  }

  private:
  void assign_new_state() {
    trie.emplace_back(26, EMPTY);
    vals.push_back(0);
    num_c.push_back(0);
    len.push_back(1);
    end.push_back(0);
  };
};

void Main() {
  int N;
  cin >> N;
  Trie<int> trie;
  vector<string> S(N);

  rep(i, N) {
    cin >> S[i];
    trie.add_word(S[i], 1);
  }

  vi &val = trie.vals;
  vvi &tri = trie.trie;
  vb &end = trie.end;
  vi &num_c = trie.num_c;
  vi &len = trie.len;

  int T = SZ(val);

  rrep(i, T) {
    rep(j, 26) if (tri[i][j] != trie.EMPTY) {
      val[i] += val[tri[i][j]];
    }
  }

  function<void(int)> dfs = [&](int now) {
    rep(i, 26) {
      int cur = tri[now][i];
      if (cur != trie.EMPTY) {
        if (num_c[cur] == 1 && !end[cur]) {
          // 子の子が1つ
          int l = 1;
          while (num_c[cur] == 1 && !end[cur]) {
            rep(j, 26) {
              if (tri[cur][j] != trie.EMPTY) {
                cur = tri[cur][j];
                break;
              }
            }
            l++;
          }
          //_p("%d:%d: %d\n", now, i, cur);
          tri[now][i] = cur;
          len[tri[now][i]] = l;
        }
        dfs(tri[now][i]);
      }
    }
  };
  dfs(0);

  //rep(ii,SZ(tri)) { cout << "tri["<<ii<<"]:"; rep(jj, SZ(tri[ii])) cout << ' ' << tri[ii][jj]; cout << endl; }
  //cout << "len:"; rep(ii,SZ(len)) cout << ' ' << len[ii]; cout << endl;
  //cout << "val:"; rep(ii,SZ(val)) cout << ' ' << val[ii]; cout << endl;

  int Q;
  cin >> Q;

  while (Q--) {
    int k; string p;
    cin >> k >> p;
    k--;
    const string &s = S[k];
    vector<vb> t(26, vb(26));
    rep(i, 26) {
      char f = p[i];
      rep(j, i+1, 26) {
        char l = p[j];
        t[f-'a'][l-'a'] = 1;
        t[l-'a'][f-'a'] = 0;
      }
    }

    //cout<<"s: "<<s<<endl;

    int n = SZ(s);
    int now = 0;
    int ans = 0;
    int pos = 0;
    while (pos < n) {
      int c = s[pos] - 'a';
      //_p("%d\n", c);
      rep(i, 26) if (tri[now][i] != trie.EMPTY) {
        if (t[i][c]) {
          ans += val[tri[now][i]];
        }
      }
      if (end[now]) ans++;
      now = tri[now][c];
      pos += len[now];
    }
    cout << ans+1 << endl;
  }
}
int main() { cin.tie(0); ios::sync_with_stdio(false); Main(); return 0; }

Submission Info

Compile Error

./Main.cpp: In function ‘int i()’:
./Main.cpp:23:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 int i() { int i; scanf("%d", &i); return i;}
                                 ^
./Main.cpp: In function ‘int l()’:
./Main.cpp:24:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 int l() { ll l; scanf("%lld", &l); return l;}
                                  ^
./Main.cpp: In function ‘vi ia(int)’:
./Main.cpp:25:56: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 vi ia(int n) {vi ret(n); rep(i, n) scanf("%d", &ret[i]); return ret;}
                                                        ^
./Main.cpp: In function ‘vl la(int)’:
./Main.cpp:26:58: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 vl la...

Judge Result