Submission #936142

#	Time	Username	Problem	Language	Result	Execution time	Memory
936142		AdamGS	Selling RNA Strands (JOI16_selling_rna)	C++17	100 / 100	464 ms	433516 KiB

selling_rna

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef struct item1 * pitem1;
typedef struct item2 * pitem2;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
struct item2 {
  pitem2 nxt[4]={nullptr, nullptr, nullptr, nullptr};
  int ile=0;
};
struct item1 {
  pitem1 nxt[4]={nullptr, nullptr, nullptr, nullptr};
  vector<int>pyt;
  pitem2 tr=nullptr;
};
vector<int>koduj(string s) {
  vector<int>P;
  for(auto i : s) {
    if(i=='A') P.pb(0);
    else if(i=='G') P.pb(1);
    else if(i=='C') P.pb(2);
    else P.pb(3);
  }
  return P;
}
const int LIM=1e5+7;
vector<int>V[LIM];
int wynik[LIM];
void dodaj2(pitem2 v, vector<int>&P, int x) {
  v->ile+=1;
  if(x==0) return;
  if(v->nxt[P[x-1]]==nullptr) v->nxt[P[x-1]]=new item2();
  dodaj2(v->nxt[P[x-1]], P, x-1);
}
void dodaj(pitem1 v, vector<int>&P, int x) {
  if(x==P.size()) {
    if(v->tr==nullptr) v->tr=new item2();
    dodaj2(v->tr, P, P.size());
    return;
  }
  if(v->nxt[P[x]]==nullptr) v->nxt[P[x]]=new item1();
  dodaj(v->nxt[P[x]], P, x+1);
}
void dodaj_pyt(pitem1 v, vector<int>&P, int x, int ind) {
  if(x==P.size()) {
    v->pyt.pb(ind);
    return;
  }
  if(v->nxt[P[x]]==nullptr) return;
  dodaj_pyt(v->nxt[P[x]], P, x+1, ind);
}
void lacz(pitem2 a, pitem2 b) {
  a->ile+=b->ile;
  rep(i, 4) if(b->nxt[i]!=nullptr) {
    if(a->nxt[i]==nullptr) a->nxt[i]=new item2();
    lacz(a->nxt[i], b->nxt[i]);
  }
}
pitem2 merguj(pitem2 a, pitem2 b) {
  if(a==nullptr) return b;
  if(b==nullptr) return a;
  if(a->ile<b->ile) swap(a, b);
  lacz(a, b);
  return a;
}
int zejdz(pitem2 v, vector<int>&P, int x) {
  if(x==P.size()) return v->ile;
  if(v->nxt[P[x]]==nullptr) return 0;
  return zejdz(v->nxt[P[x]], P, x+1);
}
void solve(pitem1 v) {
  rep(i, 4) if(v->nxt[i]!=nullptr) {
    solve(v->nxt[i]);
    v->tr=merguj(v->tr, v->nxt[i]->tr);
  }
  for(auto i : v->pyt) {
    wynik[i]=zejdz(v->tr, V[i], 0);
  }
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  pitem1 root=new item1();
  int n, m;
  cin >> n >> m;
  rep(i, n) {
    string s;
    cin >> s;
    vector<int>P=koduj(s);
    dodaj(root, P, 0);
  }
  rep(i, m) {
    string a, b;
    cin >> a >> b;
    vector<int>P=koduj(a);
    V[i]=koduj(b);
    reverse(all(V[i]));
    dodaj_pyt(root, P, 0, i);
  }
  solve(root);
  rep(i, m) cout << wynik[i] << '\n';
}

Compilation message (stderr)

selling_rna.cpp: In function 'void dodaj(pitem1, std::vector<int>&, int)':
selling_rna.cpp:41:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   if(x==P.size()) {
      |      ~^~~~~~~~~~
selling_rna.cpp: In function 'void dodaj_pyt(pitem1, std::vector<int>&, int, int)':
selling_rna.cpp:50:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   if(x==P.size()) {
      |      ~^~~~~~~~~~
selling_rna.cpp: In function 'int zejdz(pitem2, std::vector<int>&, int)':
selling_rna.cpp:72:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   if(x==P.size()) return v->ile;
      |      ~^~~~~~~~~~

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