oj.uz

Submission #129088

# Submission time Handle Problem Language Result Execution time Memory
129088 2019-07-11T15:08:34 Z mirbek01 Selling RNA Strands (JOI16_selling_rna) C++11
100 / 100
 819 ms 167544 KB 
# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

const int M = 2e6 + 2;

int n, m, ans[N], us[M];
int bor[2][4][M], cnt;
string s[N];
vector < pair <int, int> > qe[M];
vector < int > ft[M];

int get(char ch){
      if(ch == 'A')
            return 0;
      if(ch == 'C')
            return 1;
      if(ch == 'G')
            return 2;
      return 3;
}

void add(string s, int tp){
      int v = 0;
      for(int i = 0; i < s.size(); i ++){
            int x = get(s[i]);
            if(!bor[tp][x][v])
                  bor[tp][x][v] = ++ cnt;
            v = bor[tp][x][v];
      }
}

int f_v(string s, int tp){
      int v = 0;
      for(int i = 0; i < s.size(); i ++){
            int x = get(s[i]);
            if(!bor[tp][x][v])
                  return 0;
            v = bor[tp][x][v];
      }
      return v;
}

void dfs(int v, unordered_map <int, int> &cnt){
      for(auto x : ft[v])
            cnt[x] ++;
      for(int i = 0; i < 4; i ++){
            int to = bor[0][i][v];
            if(!to)
                  continue;
            unordered_map <int, int> new_cnt;
            dfs(to, new_cnt);
            if((int)cnt.size() < (int)new_cnt.size())
                  swap(cnt, new_cnt);
            for(auto x : new_cnt)
                  cnt[x.first] += x.second;
      }
      for(auto x : qe[v]){
            ans[x.second] += cnt[x.first];
      }
}

int main(){
      scanf("%d %d", &n, &m);

      for(int i = 1; i <= n; i ++)
            cin >> s[i];

      for(int i = 1; i <= n; i ++){
            add(s[i], 0);
      }

      cnt = 0;
      for(int i = 1; i <= n; i ++){
            reverse(s[i].begin(), s[i].end());
            add(s[i], 1);
      }

      for(int i = 1; i <= m; i ++){
            string pf, sf;
            cin >> pf >> sf;
            reverse(sf.begin(), sf.end());
            int v1 = f_v(pf, 0), v2 = f_v(sf, 1);
            if(!v1 || !v2)
                  continue;
            qe[v1].emplace_back( make_pair(v2, i) );
            us[v2] = 1;
      }

      for(int i = 1; i <= n; i ++){
            int v1 = 0, v2 = 0;
            reverse(s[i].begin(), s[i].end());
            v1 = f_v(s[i], 0);
            reverse(s[i].begin(), s[i].end());
            for(int j = 0; j < s[i].size(); j ++){
                  int x = get(s[i][j]);
                  v2 = bor[1][x][v2];
                  if(us[v2]){
                        ft[v1].emplace_back(v2);
                  }
            }
      }

      unordered_map<int, int> cnt;
      dfs(0, cnt);

      for(int i = 1; i <= m; i ++){
            printf("%d\n", ans[i]);
      }
}

Compilation message

selling_rna.cpp: In function 'void add(std::__cxx11::string, int)':
selling_rna.cpp:27:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < s.size(); i ++){
                      ~~^~~~~~~~~~
selling_rna.cpp: In function 'int f_v(std::__cxx11::string, int)':
selling_rna.cpp:37:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < s.size(); i ++){
                      ~~^~~~~~~~~~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:97:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0; j < s[i].size(); j ++){
                            ~~^~~~~~~~~~~~~
selling_rna.cpp:66:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &n, &m);
       ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 97528 KB Output is correct
2 Correct 90 ms 97404 KB Output is correct
3 Correct 92 ms 97412 KB Output is correct
4 Correct 91 ms 97464 KB Output is correct
5 Correct 92 ms 97400 KB Output is correct
6 Correct 93 ms 97528 KB Output is correct
7 Correct 92 ms 97400 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 439 ms 136476 KB Output is correct
2 Correct 448 ms 134648 KB Output is correct
3 Correct 773 ms 145564 KB Output is correct
4 Correct 819 ms 144828 KB Output is correct
5 Correct 491 ms 145312 KB Output is correct
6 Correct 490 ms 145912 KB Output is correct
7 Correct 679 ms 167544 KB Output is correct
8 Correct 560 ms 118740 KB Output is correct
9 Correct 569 ms 122716 KB Output is correct
10 Correct 448 ms 119040 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 99064 KB Output is correct
2 Correct 138 ms 98864 KB Output is correct
3 Correct 149 ms 99208 KB Output is correct
4 Correct 139 ms 98612 KB Output is correct
5 Correct 140 ms 98908 KB Output is correct
6 Correct 150 ms 99088 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 97528 KB Output is correct
2 Correct 90 ms 97404 KB Output is correct
3 Correct 92 ms 97412 KB Output is correct
4 Correct 91 ms 97464 KB Output is correct
5 Correct 92 ms 97400 KB Output is correct
6 Correct 93 ms 97528 KB Output is correct
7 Correct 92 ms 97400 KB Output is correct
8 Correct 439 ms 136476 KB Output is correct
9 Correct 448 ms 134648 KB Output is correct
10 Correct 773 ms 145564 KB Output is correct
11 Correct 819 ms 144828 KB Output is correct
12 Correct 491 ms 145312 KB Output is correct
13 Correct 490 ms 145912 KB Output is correct
14 Correct 679 ms 167544 KB Output is correct
15 Correct 560 ms 118740 KB Output is correct
16 Correct 569 ms 122716 KB Output is correct
17 Correct 448 ms 119040 KB Output is correct
18 Correct 154 ms 99064 KB Output is correct
19 Correct 138 ms 98864 KB Output is correct
20 Correct 149 ms 99208 KB Output is correct
21 Correct 139 ms 98612 KB Output is correct
22 Correct 140 ms 98908 KB Output is correct
23 Correct 150 ms 99088 KB Output is correct
24 Correct 456 ms 130904 KB Output is correct
25 Correct 482 ms 131576 KB Output is correct
26 Correct 441 ms 130552 KB Output is correct
27 Correct 733 ms 139000 KB Output is correct
28 Correct 546 ms 112248 KB Output is correct
29 Correct 370 ms 102892 KB Output is correct