oj.uz

Submission #243940

# Submission time Handle Problem Language Result Execution time Memory
243940 2020-07-02T09:37:48 Z fedoseevtimofey Selling RNA Strands (JOI16_selling_rna) C++14
10 / 100
 1500 ms 65272 KB 
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;

const int L = 2e6 + 7;

string rev(string s) {
  reverse(s.begin(), s.end());
  return s;
} 

int get_id(char c) {
  if (c == 'A') {
    return 0;
  } else if (c == 'G') {
    return 1;
  } else if (c == 'C') {
    return 2;
  } else {
    return 3;
  }
}

int go[L][4];
int l[L], r[L];

int uk = 2;

int add(string s, int rt) {
  int v = rt;
  for (char c : s) {
    int id = get_id(c);
    if (go[v][id] == 0) {
      go[v][id] = uk++;
    }
    v = go[v][id];
  }
  return v;
}

int find_string(string s, int rt) {
  int v = rt;
  for (char c : s) {
    int id = get_id(c);
    if (go[v][id] == 0) return -1;
    v = go[v][id];
  }
  return v;
}

vector <int> e;

void dfs(int u) {
  e.push_back(u);
  l[u] = (int)e.size() - 1;
  for (int i = 0; i < 4; ++i) {
    if (go[u][i] != 0) {
      dfs(go[u][i]);
    }
  }
  r[u] = (int)e.size() - 1;
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n, m;
  cin >> n >> m;
  int rt1 = 0, rt2 = 1;
  vector <vector <int>> where(2, vector <int> (n));
  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    where[0][i] = add(s, rt1);
    where[1][i] = add(rev(s), rt2);
  }

  dfs(rt1); 
  e.clear();
  dfs(rt2);
  for (int i = 0; i < m; ++i) {
    string p, q;
    cin >> p >> q;
    q = rev(q);
    int s1 = find_string(p, rt1), s2 = find_string(q, rt2);
    if (s1 == -1 || s2 == -1) {
      cout << "0\n";
      continue;
    }
    int ans = 0;
    for (int j = 0; j < n; ++j) {
      if ((l[s1] <= l[where[0][j]] && l[where[0][j]] <= r[s1]) && (l[s2] <= l[where[1][j]] && l[where[1][j]] <= r[s2])) {
        ++ans;
      }
    } 
    cout << ans << '\n';
  } 
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 58628 KB Output is correct
2 Correct 348 ms 55632 KB Output is correct
3 Correct 245 ms 57824 KB Output is correct
4 Correct 313 ms 55124 KB Output is correct
5 Runtime error 94 ms 65272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1595 ms 1328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 156 ms 58628 KB Output is correct
9 Correct 348 ms 55632 KB Output is correct
10 Correct 245 ms 57824 KB Output is correct
11 Correct 313 ms 55124 KB Output is correct
12 Runtime error 94 ms 65272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -