oj.uz

Submission #706951

# Submission time Handle Problem Language Result Execution time Memory
706951 2023-03-08T07:12:49 Z LittleCube Viruses (BOI20_viruses) C++14
36 / 100
 27 ms 2644 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pliii tuple<ull, int, int, int>
#define F first
#define S second
using namespace std;

struct AhoCosarick
{
    int child[55][2] = {{}}, fail[55] = {}, jump[55][2] = {{}}, idx = 0, has[55] = {};
    void insert(int pos, vector<int> &s, int i = 0)
    {
        if (!child[i][s[pos]])
            child[i][s[pos]] = ++idx;
        if (pos + 1 < s.size())
            insert(pos + 1, s, child[i][s[pos]]);
        else
            has[child[i][s[pos]]] = 1;
    }
    void build_fail()
    {
        fail[0] = -1;
        queue<int> q;
        q.push(0);
        while (!q.empty())
        {
            int i = q.front();
            q.pop();
            for (int j = 0; j <= 1; j++)
            {
                if (child[i][j])
                    jump[i][j] = child[i][j];
                else if (fail[i] >= 0)
                    jump[i][j] = jump[fail[i]][j];
            }
            if (fail[i] >= 0)
                fail[i] |= has[fail[i]];
            // cout << i << (has[i] ? '*' : ' ') << " -> " << jump[i][0] << ' ' << jump[i][1] << '\n';
            for (int j = 0; j <= 1; j++)
                if (child[i][j])
                {
                    int cur = fail[i];
                    while (cur >= 0)
                    {
                        if (child[cur][j])
                            break;
                        cur = fail[cur];
                    }
                    if (cur == -1)
                        fail[child[i][j]] = 0;
                    else
                        fail[child[i][j]] = child[cur][j];
                    q.push(child[i][j]);
                }
        }
    }
} ac;

int G, N, M, pG;
const ull inf = 1LL << 63;
ull dp[205][55][55];
vector<tuple<int, int, int>> tr[205];
priority_queue<pliii, vector<pliii>, greater<pliii>> pq;

signed main()
{
    cin >> G >> N >> M;
    pG = G;
    for (int i = 1; i <= N; i++)
    {
        int a, k;
        cin >> a >> k;
        vector<int> b(k);
        for (int j = 0; j < k; j++)
            cin >> b[j];

        while (b.size() >= 3)
        {
            int y = b.back();
            b.pop_back();
            int x = b.back();
            b.pop_back();
            tr[x].emplace_back(make_tuple(G, y, 1));
            tr[y].emplace_back(make_tuple(G, x, 2));
            b.emplace_back(G);
            G++;
        }

        if (b.size() == 1)
            tr[b[0]].emplace_back(make_tuple(a, -1, 0));
        else
        {
            tr[b[0]].emplace_back(make_tuple(a, b[1], 1));
            tr[b[1]].emplace_back(make_tuple(a, b[0], 2));
        }
    }
    for (int i = 1; i <= M; i++)
    {
        int l;
        cin >> l;
        vector<int> s(l);
        for (int j = 0; j < l; j++)
            cin >> s[j];
        ac.insert(0, s);
    }
    ac.build_fail();
    int L = ac.idx;
    for (int i = 0; i < G; i++)
        for (int j = 0; j <= L; j++)
            for (int k = 0; k <= L; k++)
                dp[i][j][k] = inf;
    for (int i = 0; i <= L; i++)
    {
        if (!ac.has[ac.jump[i][0]])
        {
            dp[0][i][ac.jump[i][0]] = 1;
            pq.push(make_tuple(1, 0, i, ac.jump[i][0]));
        }
        if (!ac.has[ac.jump[i][1]])
        {
            dp[1][i][ac.jump[i][1]] = 1;
            pq.push(make_tuple(1, 1, i, ac.jump[i][1]));
        }
    }
    while (!pq.empty())
    {
        auto [w, i, l, r] = pq.top();
        pq.pop();
        if (dp[i][l][r] < w)
            continue;
        for (auto [k, j, t] : tr[i])
            if (t == 0)
            {
                if (dp[k][l][r] > dp[i][l][r])
                {
                    dp[k][l][r] = dp[i][l][r];
                    pq.push(make_tuple(dp[k][l][r], k, l, r));
                }
            }
            else if (t == 1)
            {
                for (int e = 0; e <= L; e++)
                    if (dp[k][l][e] > dp[i][l][r] + dp[j][r][e])
                    {
                        dp[k][l][e] = dp[i][l][r] + dp[j][r][e];
                        pq.push(make_tuple(dp[k][l][e], k, l, e));
                    }
            }
            else if (t == 2)
            {
                for (int s = 0; s <= L; s++)
                    if (dp[k][s][r] > dp[j][s][l] + dp[i][l][r])
                    {
                        dp[k][s][r] = dp[j][s][l] + dp[i][l][r];
                        pq.push(make_tuple(dp[k][s][r], k, s, r));
                    }
            }
    }

    for (int i = 2; i < pG; i++)
    {
        ull ans = inf;
        for (int j = 0; j <= L; j++)
            ans = min(ans, dp[i][0][j]);
        if (ans >= inf)
            cout << "YES\n";
        else
            cout << "NO " << ans << '\n';
    }
}

Compilation message

Viruses.cpp: In member function 'void AhoCosarick::insert(int, std::vector<int>&, int)':
Viruses.cpp:18:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         if (pos + 1 < s.size())
      |             ~~~~~~~~^~~~~~~~~~
Viruses.cpp: In function 'int main()':
Viruses.cpp:130:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  130 |         auto [w, i, l, r] = pq.top();
      |              ^
Viruses.cpp:134:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  134 |         for (auto [k, j, t] : tr[i])
      |                   ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 692 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 436 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 692 KB Output is correct
3 Correct 1 ms 1460 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1748 KB Output is correct
8 Correct 1 ms 2004 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1460 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 1 ms 2004 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 568 KB Output is correct
13 Correct 1 ms 568 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 0 ms 468 KB Output is correct
20 Correct 1 ms 444 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 4 ms 1116 KB Output is correct
26 Correct 1 ms 1492 KB Output is correct
27 Correct 27 ms 1748 KB Output is correct
28 Correct 3 ms 1876 KB Output is correct
29 Correct 22 ms 1368 KB Output is correct
30 Correct 21 ms 1456 KB Output is correct
31 Correct 4 ms 1876 KB Output is correct
32 Correct 2 ms 2004 KB Output is correct
33 Correct 2 ms 1364 KB Output is correct
34 Correct 20 ms 1348 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 692 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 436 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Incorrect 1 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 692 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 436 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 1460 KB Output is correct
22 Correct 1 ms 2644 KB Output is correct
23 Correct 1 ms 1492 KB Output is correct
24 Correct 1 ms 1492 KB Output is correct
25 Correct 1 ms 1748 KB Output is correct
26 Correct 1 ms 2004 KB Output is correct
27 Correct 1 ms 1236 KB Output is correct
28 Incorrect 1 ms 340 KB Output isn't correct
29 Halted 0 ms 0 KB -