oj.uz

Submission #243941

# Submission time Handle Problem Language Result Execution time Memory
243941 2020-07-02T09:39:01 Z fedoseevtimofey Selling RNA Strands (JOI16_selling_rna) C++14
35 / 100
 1500 ms 67680 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 = 4e6 + 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 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 54628 KB Output is correct
2 Correct 343 ms 51808 KB Output is correct
3 Correct 243 ms 53980 KB Output is correct
4 Correct 305 ms 51280 KB Output is correct
5 Correct 360 ms 65760 KB Output is correct
6 Correct 335 ms 67680 KB Output is correct
7 Correct 56 ms 5880 KB Output is correct
8 Correct 247 ms 42852 KB Output is correct
9 Correct 217 ms 36856 KB Output is correct
10 Correct 161 ms 34152 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1582 ms 896 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 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 147 ms 54628 KB Output is correct
9 Correct 343 ms 51808 KB Output is correct
10 Correct 243 ms 53980 KB Output is correct
11 Correct 305 ms 51280 KB Output is correct
12 Correct 360 ms 65760 KB Output is correct
13 Correct 335 ms 67680 KB Output is correct
14 Correct 56 ms 5880 KB Output is correct
15 Correct 247 ms 42852 KB Output is correct
16 Correct 217 ms 36856 KB Output is correct
17 Correct 161 ms 34152 KB Output is correct
18 Execution timed out 1582 ms 896 KB Time limit exceeded
19 Halted 0 ms 0 KB -