oj.uz

Submission #938077

# Submission time Handle Problem Language Result Execution time Memory
938077 2024-03-04T19:21:49 Z codefox Selling RNA Strands (JOI16_selling_rna) C++14
60 / 100
 1500 ms 284036 KB 
#include <bits/stdc++.h>

using namespace std;

int N = 3*1e6;

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    int n, m;
    cin >> n >> m;

    vector<array<int, 4>> prefix(N, {-1, -1, -1, -1});
    vector<array<int, 4>> suffix(N, {-1, -1, -1, -1});
    vector<int> preind(N, -1);
    vector<int> sufind(N, -1);

    vector<vector<int>> pnodes(N);
    vector<vector<int>> snodes(N);

    vector<int> alph(300);
    alph['A'] = 0;
    alph['C'] = 1;
    alph['G'] = 2;
    alph['U'] = 3; 

    vector<string> ns(n);
    vector<int> pind(m);
    vector<int> sind(m);
    map<string, int> mp;
    map<string, int> ms;
    int cp = 0;
    int cs = 0;
    int dp = 0;
    int ds = 0;

    for (int i = 0; i < n; i++) cin >> ns[i];

    for (int i = 0; i < m; i++)
    {
        string a, b;
        cin >> a >> b;
        reverse(b.begin(), b.end());

        if (mp[a]==0) 
        {
            pind[i] = ++dp;
            mp[a] = dp;
            int curr = 0;
            for (char c:a)
            {
                int next = alph[c];
                if (prefix[curr][next]==-1)
                {
                    prefix[curr][next] = ++cp;
                }   
                curr = prefix[curr][next];
            }
            preind[curr] = dp;
        }
        else pind[i] = mp[a];
        
        if (ms[b]==0) 
        {
            sind[i] = ++ds;
            ms[b] = ds;
            int curr = 0;
            for (char c:b)
            {
                int next = alph[c];
                if (suffix[curr][next]==-1)
                {
                    suffix[curr][next] = ++cs;
                }   
                curr = suffix[curr][next];
            }
            sufind[curr] = ds;
        }
        else sind[i] = ms[b];
    }


    for (int i = 0; i < n; i++)
    {
        int curr = 0;
        for (char c:ns[i])
        {
            int next = alph[c];
            curr = prefix[curr][next];
            if (curr == -1) break;
            if (preind[curr]!=-1) pnodes[preind[curr]].push_back(i);
        }
        reverse(ns[i].begin(), ns[i].end());
        curr = 0;
        for (char c:ns[i])
        {
            int next = alph[c];
            curr = suffix[curr][next];
            if (curr == -1) break;
            if (sufind[curr]!=-1)  snodes[sufind[curr]].push_back(i);
        }
    }

    for (int i = 0; i < m; i++)
    {
        int p1 = 0;
        int p2 = 0;
        int sol = 0;
        while (p1 < pnodes[pind[i]].size() && p2 < snodes[sind[i]].size())
        {
            if (pnodes[pind[i]][p1] == snodes[sind[i]][p2]) sol++;
            if (pnodes[pind[i]][p1] > snodes[sind[i]][p2]) p2++;
            else p1++;
        }
        cout << sol << "\n";
    }

    return 0;
}

Compilation message

selling_rna.cpp: In function 'int main()':
selling_rna.cpp:111:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         while (p1 < pnodes[pind[i]].size() && p2 < snodes[sind[i]].size())
      |                ~~~^~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:111:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         while (p1 < pnodes[pind[i]].size() && p2 < snodes[sind[i]].size())
      |                                               ~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 258676 KB Output is correct
2 Correct 68 ms 258600 KB Output is correct
3 Correct 66 ms 258752 KB Output is correct
4 Correct 66 ms 258640 KB Output is correct
5 Correct 77 ms 258640 KB Output is correct
6 Correct 64 ms 258640 KB Output is correct
7 Correct 67 ms 258644 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 269648 KB Output is correct
2 Correct 176 ms 277248 KB Output is correct
3 Correct 165 ms 275332 KB Output is correct
4 Correct 218 ms 276656 KB Output is correct
5 Correct 127 ms 265648 KB Output is correct
6 Correct 124 ms 265592 KB Output is correct
7 Correct 196 ms 284036 KB Output is correct
8 Correct 179 ms 270344 KB Output is correct
9 Correct 180 ms 271168 KB Output is correct
10 Correct 160 ms 270420 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1298 ms 261528 KB Output is correct
2 Correct 855 ms 261172 KB Output is correct
3 Correct 1418 ms 262296 KB Output is correct
4 Correct 353 ms 261328 KB Output is correct
5 Correct 816 ms 261520 KB Output is correct
6 Correct 1414 ms 261976 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 258676 KB Output is correct
2 Correct 68 ms 258600 KB Output is correct
3 Correct 66 ms 258752 KB Output is correct
4 Correct 66 ms 258640 KB Output is correct
5 Correct 77 ms 258640 KB Output is correct
6 Correct 64 ms 258640 KB Output is correct
7 Correct 67 ms 258644 KB Output is correct
8 Correct 145 ms 269648 KB Output is correct
9 Correct 176 ms 277248 KB Output is correct
10 Correct 165 ms 275332 KB Output is correct
11 Correct 218 ms 276656 KB Output is correct
12 Correct 127 ms 265648 KB Output is correct
13 Correct 124 ms 265592 KB Output is correct
14 Correct 196 ms 284036 KB Output is correct
15 Correct 179 ms 270344 KB Output is correct
16 Correct 180 ms 271168 KB Output is correct
17 Correct 160 ms 270420 KB Output is correct
18 Correct 1298 ms 261528 KB Output is correct
19 Correct 855 ms 261172 KB Output is correct
20 Correct 1418 ms 262296 KB Output is correct
21 Correct 353 ms 261328 KB Output is correct
22 Correct 816 ms 261520 KB Output is correct
23 Correct 1414 ms 261976 KB Output is correct
24 Correct 431 ms 274136 KB Output is correct
25 Correct 999 ms 271292 KB Output is correct
26 Correct 338 ms 277076 KB Output is correct
27 Correct 405 ms 274140 KB Output is correct
28 Execution timed out 1541 ms 279944 KB Time limit exceeded
29 Halted 0 ms 0 KB -