제출 #866927

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
866927		catlover	Selling RNA Strands (JOI16_selling_rna)	C++17	0 / 100	213 ms	254060 KiB

selling_rna

// cre: Nguyen Hoang Hung - Train VOI 2024

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)

#define debug(x) { cerr << #x << " = "; cerr << (x) << endl; }
#define PR(a,n) { cerr << #a << " = "; FOR(_,1,n) cerr << a[_] << ' '; cerr << endl; }
#define PR0(a,n) { cerr << #a << " = "; REP(_,n) cerr << a[_] << ' '; cerr << endl; }

#define bit(X, i) ((X >> i) & 1)
#define cntbit(X) __builtin_popcountll(X)
#define fi first
#define se second
#define pb push_back
#define all(X) begin(X), end(X)
#define SZ(X) ((int)(X).size())
#define RR(X) X.resize(unique(all(X)) - begin(X))
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

using namespace std;

template <typename T>
bool maximize(T &x, T y)
{
  if(x < y)
    x = y;
  else
    return 0;
  return 1;
}
template <typename T>
bool minimize(T &x, T y)
{
  if(x > y)
    x = y;
  else
    return 0;
  return 1;
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

ll Rand(ll l, ll r) { return l + rand() % (r - l + 1); }

const int maxN = 1e6;
const ll inf = 1e18+7;
const int MOD = 1e9 + 7;
const double PI = acos(-1);

/*
-------------------------------------------------------------------------------------
    END OF TEMPLATE
-------------------------------------------------------------------------------------
    Nguyen Hoang Hung - catlover
    Training for VOI24 gold medal
-------------------------------------------------------------------------------------
*/

int convert(char c)
{
    if(c == 'A') return 0;
    if(c == 'U') return 1;
    if(c == 'G') return 2;
    return 3;
}

/////////////////////////////////////////////////////////
/**
    BUILD TRIE
**/

struct Trie
{
    Trie *ch[4];
    vector<int> vt;
    int tin, tout;
    Trie()
    {
        FOR(i, 0, 3) ch[i] = NULL;
        tin = tout = 0;
        vt.resize(0);
    }
} T, rev_T;

int pos[maxN+5];

void add(string s, int id)
{
    Trie *p = &T;
    for(char x : s)
    {
        int c = convert(x);
        if(p->ch[c] == NULL) p->ch[c] = new Trie;
        p = p->ch[c];
    }
    p->vt.pb(id);
}

void rev_add(string s, int id)
{
    Trie *p = &rev_T;
    for(char x : s)
    {
        int c = convert(x);
        if(p->ch[c] == NULL) p->ch[c] = new Trie;
        p = p->ch[c];
        p->vt.pb(pos[id]);
    }
}

/////////////////////////////////////////////////////////
/**
    EULER TOUR
**/

int Time = 0;

void dfs(Trie *p)
{
    p->tin = ++Time;
    if(SZ(p->vt) > 0)
    {
        for(int x : p->vt) pos[x] = Time;
    }
    FOR(i, 0, 3)
        if(p->ch[i] != NULL) dfs(p->ch[i]);
    p->tout = Time;
}

void dfs_rev(Trie *p)
{
    sort(all(p->vt));
    FOR(i, 0, 3)
        if(p->ch[i] != NULL) dfs(p->ch[i]);
}

pii getRange(string s)
{
    Trie *p = &T;
    for(char x : s)
    {
        int c = convert(x);
        if(p->ch[c] == NULL) return make_pair(0, 0);
        p = p->ch[c];
    }
    return make_pair(p->tin, p->tout);
}

int getAns(string s, pii Range)
{
    Trie *p = &rev_T;
    for(char x : s)
    {
        int c = convert(x);
        if(p->ch[c] == NULL) return 0;
        p = p->ch[c];
    }
    int le = lower_bound(all(p->vt), Range.fi) - p->vt.begin();
    int ri = upper_bound(all(p->vt), Range.se) - p->vt.begin() - 1;
    return ri - le + 1;
}

string s[maxN+5];

void solve() {
    int N, M;   cin >> N >> M;
    FOR(i, 1, N)
    {
        cin >> s[i];
        add(s[i], i);
        reverse(all(s[i]));
    }
    dfs(&T);
    FOR(i, 1, N)
    {
        rev_add(s[i], i);
    }
    dfs_rev(&rev_T);
    while(M --> 0)
    {
        string P, Q;
        cin >> P >> Q;
        reverse(all(Q));
        pii Range = getRange(P);
//        cout << Range.fi << ' ' << Range.se << endl;
        cout << getAns(Q, Range) << '\n';
    }
}

void solve_TestCase() {
  int testcase; cin >> testcase;

  while(testcase --> 0)
  {
    solve();
  }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    file("RNA");

//    solve_TestCase();

    solve();

    cerr << "\nTime : " << clock()/1000.0 << "s\n";

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:22:57: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:208:5: note: in expansion of macro 'file'
  208 |     file("RNA");
      |     ^~~~
selling_rna.cpp:22:90: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 | #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:208:5: note: in expansion of macro 'file'
  208 |     file("RNA");
      |     ^~~~

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