#2197009

Solution for 2257: Sakura Poetry by ei1333

Source Code Status Test Cases
    Policy: public     Reviewed: 47    
01.88 sec    7384 KB    203 lines     4574 bytes    2017-02-23 01:32
#include<bits/stdc++.h>

using namespace std;

struct TrieNode
{
  int nxt[27];

  int exist; // ???????????\????????????¨?????????????????????°????????¨?
  vector< int > accept; // ???????????????id

  TrieNode() : exist(0)
  {
    memset(nxt, -1, sizeof(nxt));
  }
};

struct Trie
{
  vector< TrieNode > nodes;
  int root;

  Trie() : root(0)
  {
    nodes.push_back(TrieNode());
  }

  virtual void direct_action(int node, int id) {}

  virtual void child_action(int node, int child, int id) {}

  void update_direct(int node, int id)
  {
    nodes[node].accept.push_back(id);
    direct_action(node, id);
  }

  void update_child(int node, int child, int id)
  {
    ++nodes[node].exist;
    child_action(node, child, id);
  }

  void add(const string &str, int str_index, int node_index, int id)
  {
    if(str_index == str.size()) {
      update_direct(node_index, id);
    } else {
      const int c = str[str_index] - 'a';
      if(nodes[node_index].nxt[c] == -1) {
        nodes[node_index].nxt[c] = (int) nodes.size();
        nodes.push_back(TrieNode());
      }
      add(str, str_index + 1, nodes[node_index].nxt[c], id);
      update_child(node_index, nodes[node_index].nxt[c], id);
    }
  }

  void add(const string &str, int id)
  {
    add(str, 0, 0, id);
  }

  void add(const string &str)
  {
    add(str, nodes[0].exist);
  }

  int size()
  {
    return (nodes[0].exist);
  }

  int nodesize()
  {
    return ((int) nodes.size());
  }
};

struct Aho_Corasick : Trie
{
  static const int FAIL = 26;
  vector< int > correct;

  Aho_Corasick() : Trie() {}

  void build()
  {
    correct.resize(nodes.size());
    for(int i = 0; i < nodes.size(); i++) {
      correct[i] = (int) nodes[i].accept.size();
    }

    queue< int > que;
    for(int i = 0; i < 27; i++) {
      if(~nodes[0].nxt[i]) {
        nodes[nodes[0].nxt[i]].nxt[FAIL] = 0;
        que.emplace(nodes[0].nxt[i]);
      } else {
        nodes[0].nxt[i] = 0;
      }
    }
    while(!que.empty()) {
      TrieNode &now = nodes[que.front()];
      correct[que.front()] += correct[now.nxt[FAIL]];
      que.pop();
      for(int i = 0; i < 26; i++) {
        if(now.nxt[i] == -1) continue;
        int fail = now.nxt[FAIL];
        while(nodes[fail].nxt[i] == -1) {
          fail = nodes[fail].nxt[FAIL];
        }
        nodes[now.nxt[i]].nxt[FAIL] = nodes[fail].nxt[i];
        que.emplace(now.nxt[i]);
      }

    }
  }

  pair< int, int > move(const string &str, int now = 0)
  {
    int match = 0;
    for(auto &c : str) {
      while(nodes[now].nxt[c - 'a'] == -1) now = nodes[now].nxt[FAIL];
      now = nodes[now].nxt[c - 'a'];
      match += correct[now];
    }
    return {now, match};
  }
};


const int mod = 1e9 + 7;

int N, M, K;
string from[250], to[250];
string seasonword[30];
unordered_map< int, int > dp[21][500][2];

int main()
{
  while(cin >> N >> M >> K, N) {

    vector< int > g[500];
    vector< string > nums;

    for(int i = 0; i < N; i++) {
      cin >> from[i] >> to[i];
      nums.push_back(from[i]);
      nums.push_back(to[i]);
    }
    for(int i = 0; i < K; i++) {
      cin >> seasonword[i];
    }

    sort(begin(nums), end(nums));
    nums.erase(unique(begin(nums), end(nums)), end(nums));
    for(int i = 0; i < N; i++) {
      int u = lower_bound(begin(nums), end(nums), from[i]) - begin(nums);
      int v = lower_bound(begin(nums), end(nums), to[i]) - begin(nums);
      g[u].push_back(v);
    }

    Aho_Corasick aho;
    for(int i = 0; i < K; i++) aho.add(seasonword[i]);
    aho.build();

    for(int i = 0; i < nums.size(); i++) {
      if(nums[i].size() > M) continue;
      auto get = aho.move(nums[i]);
      if(get.second > 1) continue;
      ++dp[nums[i].size()][i][get.second][get.first];
    }
    for(int i = 1; i < M; i++) {
      for(int j = 0; j < nums.size(); j++) {
        for(int k = 0; k < 2; k++) {
          for(auto &v : dp[i % 21][j][k]) {
            for(auto &t : g[j]) {
              if(i + nums[t].size() > M) continue;
              auto get = aho.move(nums[t], v.first);
              if(k + get.second > 1) continue;
              (dp[(i + nums[t].size()) % 21][t][k + get.second][get.first] += v.second) %= mod;
            }
          }
          dp[i % 21][j][k].clear();
        }
      }
    }
    int ret = 0;
    for(int j = 0; j < nums.size(); j++) {
      for(auto &v : dp[M % 21][j][1]) (ret += v.second) %= mod;
    }
    cout << ret << endl;


    for(int i = 0; i < 21; i++) {
      for(int j = 0; j < nums.size(); j++) {
        for(int k = 0; k < 2; k++) dp[i][j][k].clear();
      }
    }
  }
}

Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 2/2 C++11 CPU: 01.88 sec Memory: 7384 KB Length: 4574 B 2017-02-23 01:32 2017-02-23 01:32
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 01.88 sec 7384 KB
Case #2: : Accepted 00.25 sec 4624 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags