oj.uz

Submission #625181

# Submission time Handle Problem Language Result Execution time Memory
625181 2022-08-09T14:33:04 Z KoD Viruses (BOI20_viruses) C++17
100 / 100
 127 ms 7840 KB 
#include <bits/stdc++.h>

using ull = unsigned long long;
using std::vector;
using std::array;
using std::pair;

template <class T>
bool setmin(T& x, const T& y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

template <class T>
using min_heap = std::priority_queue<T, vector<T>, std::greater<>>;

class Trie {
    struct Node {
        array<int, 2> next;
        int link;
        bool bad;
        Node() : next({-1, -1}), link(-1), bad(false) {}
    };

    vector<Node> node;

  public:
    Trie() : node({Node()}) {}

    void insert(const vector<int>& str) {
        int u = 0;
        for (const int x : str) {
            if (node[u].next[x] == -1) {
                node[u].next[x] = node.size();
                node.emplace_back();
            }
            u = node[u].next[x];
        }
        node[u].bad = true;
    }

    vector<array<int, 3>> build() {
        std::queue<int> que;
        for (const int k : {0, 1}) {
            if (node[0].next[k] == -1) {
                node[0].next[k] = node.size();
                node.emplace_back();
            }
            const int u = node[0].next[k];
            node[u].link = 0;
            que.push(u);
        }
        while (!que.empty()) {
            const int u = que.front();
            que.pop();
            for (const int k : {0, 1}) {
                const int v = node[u].next[k];
                if (v == -1) {
                    continue;
                }
                que.push(v);
                int t = u;
                do {
                    t = node[t].link;
                } while (node[t].next[k] == -1);
                const int s = node[t].next[k];
                node[v].link = s;
                if (node[s].bad) {
                    node[v].bad = true;
                }
            }
        }
        const int V = node.size();
        vector<array<int, 3>> ret(V);
        for (int u = 0; u < V; ++u) {
            for (const int k : {0, 1}) {
                int v = u;
                while (node[v].next[k] == -1) {
                    v = node[v].link;
                }
                ret[u][k] = node[v].next[k];
            }
            ret[u][2] = node[u].bad;
        }
        return ret;
    }
};

struct State {
    ull d;
    int i, j, u, v;
    bool operator<(const State& other) const { return d < other.d; }
    bool operator>(const State& other) const { return d > other.d; }
};

constexpr ull inf = std::numeric_limits<ull>::max();

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int G, N, K;
    std::cin >> G >> N >> K;
    vector<int> id(N);
    vector<vector<int>> seq(N);
    for (int i = 0; i < N; ++i) {
        int k;
        std::cin >> id[i] >> k;
        seq[i].resize(k);
        for (auto& x : seq[i]) {
            std::cin >> x;
        }
    }
    Trie trie;
    while (K--) {
        int k;
        std::cin >> k;
        vector<int> str(k);
        for (auto& x : str) {
            std::cin >> x;
        }
        trie.insert(str);
    }
    const auto data = trie.build();
    const int V = data.size();
    vector complete(G, vector(V, vector(V, inf)));
    vector<vector<vector<vector<ull>>>> make(N);
    for (int i = 0; i < N; ++i) {
        make[i] = vector(seq[i].size() + 1, vector(V, vector(V, inf)));
    }
    min_heap<State> heap;
    const auto push_c = [&](const int i, const int u, const int v, const ull d) {
        if (!data[u][2] and !data[v][2] and setmin(complete[i][u][v], d)) {
            heap.push({d, i, -1, u, v});
        }
    };
    const auto push_m = [&](const int i, const int j, const int u, const int v, const ull d) {
        if (!data[u][2] and !data[v][2] and setmin(make[i][j][u][v], d)) {
            heap.push({d, i, j, u, v});
        }
    };
    for (const int k : {0, 1}) {
        for (int i = 0; i < V; ++i) {
            const int j = data[i][k];
            push_c(k, i, j, 1);
        }
    }
    for (int i = 0; i < N; ++i) {
        for (int u = 0; u < V; ++u) {
            push_m(i, 0, u, u, 0);
        }
    }
    while (!heap.empty()) {
        const auto [d, i, j, u, v] = heap.top();
        heap.pop();
        if (j == -1) {
            if (d > complete[i][u][v]) {
                continue;
            }
            for (int k = 0; k < N; ++k) {
                for (int l = 0; l < (int)seq[k].size(); ++l) {
                    if (seq[k][l] == i) {
                        for (int m = 0; m < V; ++m) {
                            if (const ull tmp = make[k][l][m][u]; tmp != inf) {
                                push_m(k, l + 1, m, v, tmp + d);
                            }
                        }
                    }
                }
            }
        } else if (j == (int)seq[i].size()) {
            push_c(id[i], u, v, d);
        } else {
            if (d > make[i][j][u][v]) {
                continue;
            }
            const int k = seq[i][j];
            for (int l = 0; l < V; ++l) {
                if (const ull tmp = complete[k][v][l]; tmp != inf) {
                    push_m(i, j + 1, u, l, d + tmp);
                }
            }
        }
    }
    for (int i = 2; i < G; ++i) {
        ull min = inf;
        for (int u = 0; u < V; ++u) {
            setmin(min, complete[i][0][u]);
        }
        if (min == inf) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO " << min << '\n';
        }
    }
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 312 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 316 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 4 ms 5076 KB Output is correct
4 Correct 7 ms 7508 KB Output is correct
5 Correct 7 ms 4800 KB Output is correct
6 Correct 4 ms 4692 KB Output is correct
7 Correct 3 ms 3772 KB Output is correct
8 Correct 3 ms 3156 KB Output is correct
9 Correct 2 ms 2368 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 980 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 1620 KB Output is correct
14 Correct 1 ms 980 KB Output is correct
15 Correct 1 ms 1236 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 1236 KB Output is correct
18 Correct 1 ms 1108 KB Output is correct
19 Correct 1 ms 1108 KB Output is correct
20 Correct 1 ms 1236 KB Output is correct
21 Correct 2 ms 1236 KB Output is correct
22 Correct 1 ms 724 KB Output is correct
23 Correct 0 ms 468 KB Output is correct
24 Correct 0 ms 340 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5076 KB Output is correct
2 Correct 7 ms 7508 KB Output is correct
3 Correct 7 ms 4800 KB Output is correct
4 Correct 4 ms 4692 KB Output is correct
5 Correct 3 ms 3772 KB Output is correct
6 Correct 3 ms 3156 KB Output is correct
7 Correct 2 ms 2368 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 316 KB Output is correct
20 Correct 1 ms 320 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 576 KB Output is correct
25 Correct 4 ms 2624 KB Output is correct
26 Correct 5 ms 6188 KB Output is correct
27 Correct 127 ms 4980 KB Output is correct
28 Correct 5 ms 3668 KB Output is correct
29 Correct 122 ms 7840 KB Output is correct
30 Correct 126 ms 6204 KB Output is correct
31 Correct 7 ms 3300 KB Output is correct
32 Correct 5 ms 3668 KB Output is correct
33 Correct 5 ms 4928 KB Output is correct
34 Correct 124 ms 7724 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 312 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 316 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 1 ms 320 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 316 KB Output is correct
34 Correct 1 ms 320 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 1 ms 576 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 1 ms 316 KB Output is correct
41 Correct 1 ms 316 KB Output is correct
42 Correct 1 ms 340 KB Output is correct
43 Correct 0 ms 340 KB Output is correct
44 Correct 1 ms 452 KB Output is correct
45 Correct 1 ms 444 KB Output is correct
46 Correct 0 ms 340 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 1 ms 456 KB Output is correct
49 Correct 0 ms 452 KB Output is correct
50 Correct 1 ms 448 KB Output is correct
51 Correct 1 ms 468 KB Output is correct
52 Correct 1 ms 468 KB Output is correct
53 Correct 1 ms 468 KB Output is correct
54 Correct 1 ms 452 KB Output is correct
55 Correct 1 ms 468 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 288 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 312 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 316 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 4 ms 5076 KB Output is correct
22 Correct 7 ms 7508 KB Output is correct
23 Correct 7 ms 4800 KB Output is correct
24 Correct 4 ms 4692 KB Output is correct
25 Correct 3 ms 3772 KB Output is correct
26 Correct 3 ms 3156 KB Output is correct
27 Correct 2 ms 2368 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 1 ms 980 KB Output is correct
30 Correct 1 ms 724 KB Output is correct
31 Correct 1 ms 1620 KB Output is correct
32 Correct 1 ms 980 KB Output is correct
33 Correct 1 ms 1236 KB Output is correct
34 Correct 1 ms 468 KB Output is correct
35 Correct 1 ms 1236 KB Output is correct
36 Correct 1 ms 1108 KB Output is correct
37 Correct 1 ms 1108 KB Output is correct
38 Correct 1 ms 1236 KB Output is correct
39 Correct 2 ms 1236 KB Output is correct
40 Correct 1 ms 724 KB Output is correct
41 Correct 0 ms 468 KB Output is correct
42 Correct 0 ms 340 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 1 ms 340 KB Output is correct
45 Correct 0 ms 340 KB Output is correct
46 Correct 1 ms 320 KB Output is correct
47 Correct 0 ms 340 KB Output is correct
48 Correct 0 ms 340 KB Output is correct
49 Correct 1 ms 340 KB Output is correct
50 Correct 1 ms 340 KB Output is correct
51 Correct 1 ms 340 KB Output is correct
52 Correct 1 ms 340 KB Output is correct
53 Correct 1 ms 340 KB Output is correct
54 Correct 1 ms 316 KB Output is correct
55 Correct 1 ms 320 KB Output is correct
56 Correct 1 ms 340 KB Output is correct
57 Correct 1 ms 340 KB Output is correct
58 Correct 1 ms 340 KB Output is correct
59 Correct 1 ms 576 KB Output is correct
60 Correct 4 ms 2624 KB Output is correct
61 Correct 5 ms 6188 KB Output is correct
62 Correct 127 ms 4980 KB Output is correct
63 Correct 5 ms 3668 KB Output is correct
64 Correct 122 ms 7840 KB Output is correct
65 Correct 126 ms 6204 KB Output is correct
66 Correct 7 ms 3300 KB Output is correct
67 Correct 5 ms 3668 KB Output is correct
68 Correct 5 ms 4928 KB Output is correct
69 Correct 124 ms 7724 KB Output is correct
70 Correct 1 ms 340 KB Output is correct
71 Correct 1 ms 316 KB Output is correct
72 Correct 1 ms 316 KB Output is correct
73 Correct 1 ms 340 KB Output is correct
74 Correct 0 ms 340 KB Output is correct
75 Correct 1 ms 452 KB Output is correct
76 Correct 1 ms 444 KB Output is correct
77 Correct 0 ms 340 KB Output is correct
78 Correct 1 ms 340 KB Output is correct
79 Correct 1 ms 456 KB Output is correct
80 Correct 0 ms 452 KB Output is correct
81 Correct 1 ms 448 KB Output is correct
82 Correct 1 ms 468 KB Output is correct
83 Correct 1 ms 468 KB Output is correct
84 Correct 1 ms 468 KB Output is correct
85 Correct 1 ms 452 KB Output is correct
86 Correct 1 ms 468 KB Output is correct
87 Correct 9 ms 2048 KB Output is correct
88 Correct 1 ms 468 KB Output is correct
89 Correct 1 ms 468 KB Output is correct
90 Correct 1 ms 1108 KB Output is correct
91 Correct 1 ms 852 KB Output is correct
92 Correct 29 ms 3328 KB Output is correct
93 Correct 19 ms 2408 KB Output is correct
94 Correct 2 ms 1728 KB Output is correct
95 Correct 1 ms 1236 KB Output is correct
96 Correct 1 ms 1620 KB Output is correct
97 Correct 6 ms 1688 KB Output is correct
98 Correct 2 ms 2004 KB Output is correct
99 Correct 10 ms 2900 KB Output is correct
100 Correct 2 ms 1748 KB Output is correct
101 Correct 3 ms 1620 KB Output is correct
102 Correct 68 ms 4364 KB Output is correct
103 Correct 4 ms 2772 KB Output is correct
104 Correct 15 ms 3156 KB Output is correct
105 Correct 2 ms 1108 KB Output is correct
106 Correct 37 ms 4432 KB Output is correct
107 Correct 37 ms 4808 KB Output is correct