oj.uz

Submission #395509

# Submission time Handle Problem Language Result Execution time Memory
395509 2021-04-28T12:16:48 Z KoD Viruses (BOI20_viruses) C++17
11 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

using ll = long long;

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

    Vec<Node> node;
    int add_node() {
        node.push_back(Node());
        return (int) node.size() - 1;
    }

    Trie() { add_node(); }

    void insert(const Vec<int>& binary) {
        int pos = 0;
        for (const auto x: binary) {
            if (node[pos].next[x] == -1) {
                node[pos].next[x] = add_node();
            }
            pos = node[pos].next[x];
        }
        node[pos].bad = true;
    }

    void build() {
        std::queue<int> que;
        for (int k = 0; k < 2; ++k) {
            if (node[0].next[k] == -1) {
                node[0].next[k] = add_node();
            }
            node[node[0].next[k]].link = 0;
            que.push(node[0].next[k]);
        }
        while (!que.empty()) {
            const auto u = que.front();
            que.pop();
            for (int k = 0; k < 2; ++k) {
                const auto v = node[u].next[k];
                if (v == -1) {
                    continue;
                }
                int p = node[u].link;
                while (node[p].next[k] == -1) {
                    p = node[p].link;
                }
                node[v].link = node[p].next[k];
                que.push(v);
            }
        }
    }
};

int main() {
    int G, N, M;
    std::cin >> G >> N >> M;
    Vec<Vec<Vec<int>>> graph(G);
    for (int i = 0; i < N; ++i) {
        int a, k;
        std::cin >> a >> k;
        Vec<int> b(k);
        for (auto& x: b) {
            std::cin >> x;
        }
        graph[a].push_back(std::move(b));
    }
    Vec<ll> shortest(G, -1);
    shortest[0] = shortest[1] = 1;
    while (true) {
        bool change = false;
        for (int i = 2; i < G; ++i) {
            for (const auto& v: graph[i]) {
                ll sum = 0;
                for (const auto x: v) {
                    if (shortest[x] == -1) {
                        sum = -1;
                        break;
                    }
                    sum += shortest[x];
                }
                if (sum != -1 and (shortest[i] == -1 or shortest[i] > sum)) {
                    shortest[i] = sum;
                    change = true;
                }
            }
        }
        if (!change) {
            break;
        }
    }
    if (M == 0) {
        for (int i = 2; i < G; ++i) {
            if (shortest[i] == -1) {
                std::cout << "YES\n";
            }
            else {
                std::cout << "NO " << shortest[i] << '\n';
            }
        }
        return 0;
    }
    Trie trie;
    for (int i = 0; i < M; ++i) {
        int k;
        std::cin >> k;
        Vec<int> c(k);
        for (auto& x: c) {
            std::cin >> x;
        }
        trie.insert(c);
    }
    trie.build();
    const auto V = (int) trie.node.size();
    Vec<bool> bad(V);
    for (int i = 0; i < V; ++i) {
        bad[i] = trie.node[i].bad;
    }
    Vec<std::array<int, 2>> to(V);
    for (int i = 0; i < V; ++i) {
        for (int k = 0; k < 2; ++k) {
            int u = i;
            while (trie.node[u].next[k] == -1) {
                u = trie.node[u].link;
            }
            to[i][k] = trie.node[u].next[k];
        }
    }
    if (N == G - 2) {
        Vec<Vec<int>> memo(G, Vec<int>(V, -2));
        auto dfs = [&](auto&& dfs, const int i, const int u) -> int {
            if (memo[i][u] != -2) {
                return memo[i][u];
            }
            if (shortest[i] == -1 or bad[u]) {
                return memo[i][u] = -1;
            }
            if (i < 2) {
                return memo[i][u] = (bad[to[u][i]] ? -1 : to[u][i]);
            }
            int v = u;
            for (const auto x: graph[i][0]) {
                v = dfs(dfs, x, v);
                if (v == -1 or bad[v]) {
                    return memo[i][u] = -1;
                }
            }
            return memo[i][u] = (bad[v] ? -1 : v);
        };
        for (int i = 2; i < G; ++i) {
            if (dfs(dfs, i, 0) == -1) {
                std::cout << "YES\n";
            }
            else {
                std::cout << "NO " << shortest[i] << '\n';
            }
        }
        return 0;
    }
    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Incorrect 1 ms 204 KB Output isn't correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Incorrect 1 ms 204 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 208 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 1 ms 204 KB Output isn't correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 208 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Incorrect 1 ms 204 KB Output isn't correct