제출 #516697

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
516697		MilosMilutinovic	Selling RNA Strands (JOI16_selling_rna)	C++14	35 / 100	1548 ms	285584 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<string> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s[i];
  }
  vector<string> L(m), R(m);
  for (int i = 0; i < m; i++) {
    cin >> L[i] >> R[i];
  }
  vector<vector<int>> trie(1, vector<int>(26, -1));
  for (int i = 0; i < n; i++) {
    int t = 0;
    for (int j = 0; j < (int) s[i].size(); j++) {
      int c = (int) (s[i][j] - 'A');
      if (trie[t][c] == -1) {
        trie[t][c] = trie.size();
        trie.emplace_back(vector<int>(26, -1));
      }
      t = trie[t][c];
    }
  }
  for (int i = 0; i < m; i++) {
    int t = 0;
    for (int j = 0; j < (int) L[i].size(); j++) {
      int c = (int) (L[i][j] - 'A');
      if (trie[t][c] == -1) {
        trie[t][c] = trie.size();
        trie.emplace_back(vector<int>(26, -1));
      }
      t = trie[t][c];
    }
  }
  int k = trie.size();
  vector<int> tl(k), tr(k);
  int T;
  function<void(int)> Dfs = [&](int u) {
    tl[u] = ++T;
    for (int i = 0; i < 26; i++) {
      if (trie[u][i] != -1) {
        Dfs(trie[u][i]);
      }
    }
    tr[u] = T;
  };
  T = 0;
  Dfs(0);
  vector<int> x(n);
  vector<int> xl(m), xr(m);
  for (int i = 0; i < n; i++) {
    int t = 0;
    for (int j = 0; j < (int) s[i].size(); j++) {
      int c = (int) (s[i][j] - 'A');
      t = trie[t][c];
    }
    x[i] = tl[t];
  }
  for (int i = 0; i < m; i++) {
    int t = 0;
    for (int j = 0; j < (int) L[i].size(); j++) {
      int c = (int) (L[i][j] - 'A');
      t = trie[t][c];
    }
    xl[i] = tl[t];
    xr[i] = tr[t];
  }
  trie.clear();
  trie.emplace_back(vector<int>(26, -1));
  for (int i = 0; i < n; i++) {
    reverse(s[i].begin(), s[i].end());
    int t = 0;
    for (int j = 0; j < (int) s[i].size(); j++) {
      int c = (int) (s[i][j] - 'A');
      if (trie[t][c] == -1) {
        trie[t][c] = trie.size();
        trie.emplace_back(vector<int>(26, -1));
      }
      t = trie[t][c];
    }
  }
  for (int i = 0; i < m; i++) {
    reverse(R[i].begin(), R[i].end());
    int t = 0;
    for (int j = 0; j < (int) R[i].size(); j++) {
      int c = (int) (R[i][j] - 'A');
      if (trie[t][c] == -1) {
        trie[t][c] = trie.size();
        trie.emplace_back(vector<int>(26, -1));
      }
      t = trie[t][c];
    }
  }
  k = trie.size();
  tl.resize(k);
  tr.resize(k);
  T = 0;
  Dfs(0);
  vector<int> y(n);
  vector<int> yl(m), yr(m);
  for (int i = 0; i < n; i++) {
    int t = 0;
    for (int j = 0; j < (int) s[i].size(); j++) {
      int c = (int) (s[i][j] - 'A');
      t = trie[t][c];
    }
    y[i] = tl[t];
  }
  for (int i = 0; i < m; i++) {
    int t = 0;
    for (int j = 0; j < (int) R[i].size(); j++) {
      int c = (int) (R[i][j] - 'A');
      t = trie[t][c];
    }
    yl[i] = tl[t];
    yr[i] = tr[t];
  }
  for (int i = 0; i < m; i++) {
    int ans = 0;
    for (int j = 0; j < n; j++) {
      if (xl[i] <= x[j] && x[j] <= xr[i] && yl[i] <= y[j] && y[j] <= yr[i]) {
        ans += 1;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 40