Submission #129089

#	Time	Username	Problem	Language	Result	Execution time	Memory
129089		mirbek01	Selling RNA Strands (JOI16_selling_rna)	C++11	100 / 100	858 ms	162168 KiB

selling_rna

# 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];

      sort(s + 1, s + n + 1);

      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 (stderr)

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:99: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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40