oj.uz

Submission #1111052

# Submission time Handle Problem Language Result Execution time Memory
1111052 2024-11-11T11:21:04 Z Zero_OP Viruses (BOI20_viruses) C++14
100 / 100
 33 ms 2640 KB 
#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))

struct AhoCorasick{
    vector<int> link, bad;
    vector<array<int, 2>> next;

    int size(){ return (int)link.size(); }
    void extend(){ link.emplace_back(-1); bad.emplace_back(0); next.emplace_back(array<int, 2>{-1, -1}); }

    AhoCorasick() : link(), bad(), next() { extend(); }

    void add(const vector<int>& s){
        int u = 0;
        for(auto c : s){
            if(next[u][c] == -1){
                next[u][c] = size();
                extend();
            }
            u = next[u][c];
        }
        bad[u] = 1;
    }

    void compute_links(){
        queue<int> q; q.push(0);
        while(!q.empty()){
            int u = q.front(), sf = link[u]; q.pop();
            if(u > 0) bad[u] |= bad[sf];
            for(int c = 0; c < 2; ++c){
                int& nxt = next[u][c], nxt_sf = (u ? next[sf][c] : 0);
                if(nxt == -1) nxt = nxt_sf;
                else{
                    link[nxt] = nxt_sf;
                    q.push(nxt);
                }
            }
        }
    }

    int go(int u, int c){ return next[u][c]; }
    int check(int u){ return !bad[u]; }
};

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b) {
            return a = b, true;
        } return false;
    }

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

    int G, N, M;
    cin >> G >> N >> M;
    int base = G;
    vector<int> from(N);
    vector<vector<int>> mutations(N);

    for(int i = 0; i < N; ++i){
        int a, k; cin >> a >> k;
        vector<int> mut(k);
        for(int &j : mut) cin >> j;

        while((int)mut.size() > 2){
            int v1 = mut[(int)mut.size() - 2];
            int v2 = mut.back();
            mut.pop_back();
            mut.pop_back();

            mutations.emplace_back();
            mutations.back().emplace_back(v1);
            mutations.back().emplace_back(v2);

            from.emplace_back(G);
            mut.push_back(G);
            ++G;
        }

        from[i] = a;
        mutations[i] = mut;
    }

    AhoCorasick T;
    for(int i = 0; i < M; ++i){
        int l; cin >> l;
        vector<int> s(l);
        for(int& j : s) cin >> j;
        T.add(s);
    }

    T.compute_links();

    int aho_size = T.size();

    using ull = unsigned long long;
    using state = tuple<ull, int, int, int>;
    const ull inf = 1ULL << 63;

    auto add = [&](ull a, ull b) -> ull{
        return (a == inf || b == inf ? inf : a + b);
    };

    vector<vector<vector<ull>>> dist(G, vector<vector<ull>>(aho_size, vector<ull>(aho_size, inf)));
    priority_queue<state, vector<state>, greater<state>> pq;

    for(int c = 0; c < 2; ++c){
        for(int u = 0; u < aho_size; ++u) if(T.check(u)){
            int v = T.go(u, c);
            if(v == -1 || !T.check(v)) continue;
            dist[c][u][v] = 1;
            pq.push({1, c, u, v});
        }
    }

    /*

    single_transform : a -> <x>
    a -> <x, y>

    transition 1 : for a -> <x>
    => dp[a][u][v] = min(dp[a][u][v], dp[x][u][v]

    transition 2 : for a -> <x, y>
    => dp[a][u][v] = min(dp[a][u][v], dp[x][u][pre] + dp[y][pre][v]

    */
    vector<vector<int>> single_transform(G), x_transform(G), y_transform(G);

    N = sz(from);
    for(int i = 0; i < N; ++i){
        assert(sz(mutations[i]) <= 2);

        if(sz(mutations[i]) == 1){
            int x = mutations[i][0];
            single_transform[x].emplace_back(i); // a -> <x>
        } else{
            int x1 = mutations[i][0], x2 = mutations[i][1];
            x_transform[x1].emplace_back(i); // -> a -> <x, ?>
            y_transform[x2].emplace_back(i); // -> a -> <?, y>
        }
    }

    while(!pq.empty()){
        ull cur; int c, u, v;
        tie(cur, c, u, v) = pq.top(); pq.pop();

        if(cur != dist[c][u][v]) continue;

        for(int id : single_transform[c]){
            int a = from[id];
            //dp[a][u][v] = dp[x][u][v]
            if(minimize(dist[a][u][v], cur)){
                pq.push({dist[a][u][v], a, u, v});
            }
        }

        for(int id : x_transform[c]){
            int a = from[id], x = c, y = mutations[id][1];
            //dp[a][u][?] = dp[x][u][v] + dp[y][v][?]
            for(int last = 0; last < aho_size; ++last){
                if(minimize(dist[a][u][last], add(cur, dist[y][v][last]))){
                    pq.push({dist[a][u][last], a, u, last});
                }
            }
        }

        for(int id : y_transform[c]){
            int a = from[id], x = mutations[id][0], y = c;
            //dp[a][?][v] = dp[x][?][u] + dp[y][u][v]
            for(int start = 0; start < aho_size; ++start){
                if(minimize(dist[a][start][v], add(dist[x][start][u], cur))){
                    pq.push({dist[a][start][v], a, start, v});
                }
            }
        }
    }

    for(int i = 2; i < base; ++i){
        ull res = inf;
        for(int u = 0; u < aho_size; ++u){
            minimize(res, dist[i][0][u]);
        }

        if(res == inf) cout << "YES\n";
        else cout << "NO " << res << '\n';
    }

    return 0;
}

Compilation message

Viruses.cpp: In function 'int main()':
Viruses.cpp:166:31: warning: unused variable 'x' [-Wunused-variable]
  166 |             int a = from[id], x = c, y = mutations[id][1];
      |                               ^
Viruses.cpp:176:53: warning: unused variable 'y' [-Wunused-variable]
  176 |             int a = from[id], x = mutations[id][0], y = c;
      |                                                     ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 508 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 388 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2 ms 1528 KB Output is correct
4 Correct 2 ms 2640 KB Output is correct
5 Correct 2 ms 1360 KB Output is correct
6 Correct 2 ms 1528 KB Output is correct
7 Correct 3 ms 1616 KB Output is correct
8 Correct 2 ms 1872 KB Output is correct
9 Correct 2 ms 1104 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 848 KB Output is correct
12 Correct 1 ms 592 KB Output is correct
13 Correct 1 ms 848 KB Output is correct
14 Correct 1 ms 592 KB Output is correct
15 Correct 2 ms 848 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 2 ms 848 KB Output is correct
18 Correct 3 ms 860 KB Output is correct
19 Correct 2 ms 1016 KB Output is correct
20 Correct 1 ms 848 KB Output is correct
21 Correct 2 ms 848 KB Output is correct
22 Correct 2 ms 592 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 336 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1528 KB Output is correct
2 Correct 2 ms 2640 KB Output is correct
3 Correct 2 ms 1360 KB Output is correct
4 Correct 2 ms 1528 KB Output is correct
5 Correct 3 ms 1616 KB Output is correct
6 Correct 2 ms 1872 KB Output is correct
7 Correct 2 ms 1104 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 508 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 436 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 5 ms 1104 KB Output is correct
26 Correct 2 ms 1360 KB Output is correct
27 Correct 33 ms 1848 KB Output is correct
28 Correct 3 ms 1872 KB Output is correct
29 Correct 31 ms 1408 KB Output is correct
30 Correct 27 ms 1608 KB Output is correct
31 Correct 5 ms 1784 KB Output is correct
32 Correct 3 ms 1872 KB Output is correct
33 Correct 3 ms 1360 KB Output is correct
34 Correct 33 ms 1204 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 508 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 388 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 1 ms 336 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 508 KB Output is correct
31 Correct 1 ms 336 KB Output is correct
32 Correct 1 ms 336 KB Output is correct
33 Correct 1 ms 436 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 1 ms 336 KB Output is correct
36 Correct 1 ms 336 KB Output is correct
37 Correct 1 ms 336 KB Output is correct
38 Correct 1 ms 336 KB Output is correct
39 Correct 1 ms 336 KB Output is correct
40 Correct 1 ms 336 KB Output is correct
41 Correct 1 ms 336 KB Output is correct
42 Correct 1 ms 336 KB Output is correct
43 Correct 1 ms 336 KB Output is correct
44 Correct 1 ms 336 KB Output is correct
45 Correct 1 ms 336 KB Output is correct
46 Correct 1 ms 336 KB Output is correct
47 Correct 1 ms 336 KB Output is correct
48 Correct 2 ms 336 KB Output is correct
49 Correct 1 ms 336 KB Output is correct
50 Correct 1 ms 472 KB Output is correct
51 Correct 1 ms 336 KB Output is correct
52 Correct 1 ms 336 KB Output is correct
53 Correct 1 ms 336 KB Output is correct
54 Correct 1 ms 424 KB Output is correct
55 Correct 1 ms 336 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 508 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 388 KB Output is correct
21 Correct 2 ms 1528 KB Output is correct
22 Correct 2 ms 2640 KB Output is correct
23 Correct 2 ms 1360 KB Output is correct
24 Correct 2 ms 1528 KB Output is correct
25 Correct 3 ms 1616 KB Output is correct
26 Correct 2 ms 1872 KB Output is correct
27 Correct 2 ms 1104 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 2 ms 848 KB Output is correct
30 Correct 1 ms 592 KB Output is correct
31 Correct 1 ms 848 KB Output is correct
32 Correct 1 ms 592 KB Output is correct
33 Correct 2 ms 848 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 2 ms 848 KB Output is correct
36 Correct 3 ms 860 KB Output is correct
37 Correct 2 ms 1016 KB Output is correct
38 Correct 1 ms 848 KB Output is correct
39 Correct 2 ms 848 KB Output is correct
40 Correct 2 ms 592 KB Output is correct
41 Correct 1 ms 336 KB Output is correct
42 Correct 1 ms 336 KB Output is correct
43 Correct 1 ms 336 KB Output is correct
44 Correct 1 ms 336 KB Output is correct
45 Correct 1 ms 336 KB Output is correct
46 Correct 1 ms 336 KB Output is correct
47 Correct 1 ms 336 KB Output is correct
48 Correct 1 ms 336 KB Output is correct
49 Correct 1 ms 336 KB Output is correct
50 Correct 1 ms 336 KB Output is correct
51 Correct 1 ms 508 KB Output is correct
52 Correct 1 ms 336 KB Output is correct
53 Correct 1 ms 336 KB Output is correct
54 Correct 1 ms 436 KB Output is correct
55 Correct 1 ms 336 KB Output is correct
56 Correct 1 ms 336 KB Output is correct
57 Correct 1 ms 336 KB Output is correct
58 Correct 1 ms 336 KB Output is correct
59 Correct 1 ms 336 KB Output is correct
60 Correct 5 ms 1104 KB Output is correct
61 Correct 2 ms 1360 KB Output is correct
62 Correct 33 ms 1848 KB Output is correct
63 Correct 3 ms 1872 KB Output is correct
64 Correct 31 ms 1408 KB Output is correct
65 Correct 27 ms 1608 KB Output is correct
66 Correct 5 ms 1784 KB Output is correct
67 Correct 3 ms 1872 KB Output is correct
68 Correct 3 ms 1360 KB Output is correct
69 Correct 33 ms 1204 KB Output is correct
70 Correct 1 ms 336 KB Output is correct
71 Correct 1 ms 336 KB Output is correct
72 Correct 1 ms 336 KB Output is correct
73 Correct 1 ms 336 KB Output is correct
74 Correct 1 ms 336 KB Output is correct
75 Correct 1 ms 336 KB Output is correct
76 Correct 1 ms 336 KB Output is correct
77 Correct 1 ms 336 KB Output is correct
78 Correct 1 ms 336 KB Output is correct
79 Correct 2 ms 336 KB Output is correct
80 Correct 1 ms 336 KB Output is correct
81 Correct 1 ms 472 KB Output is correct
82 Correct 1 ms 336 KB Output is correct
83 Correct 1 ms 336 KB Output is correct
84 Correct 1 ms 336 KB Output is correct
85 Correct 1 ms 424 KB Output is correct
86 Correct 1 ms 336 KB Output is correct
87 Correct 5 ms 1008 KB Output is correct
88 Correct 1 ms 504 KB Output is correct
89 Correct 1 ms 336 KB Output is correct
90 Correct 1 ms 592 KB Output is correct
91 Correct 1 ms 592 KB Output is correct
92 Correct 22 ms 2508 KB Output is correct
93 Correct 15 ms 1872 KB Output is correct
94 Correct 2 ms 1104 KB Output is correct
95 Correct 1 ms 848 KB Output is correct
96 Correct 1 ms 848 KB Output is correct
97 Correct 6 ms 1208 KB Output is correct
98 Correct 2 ms 1104 KB Output is correct
99 Correct 6 ms 1472 KB Output is correct
100 Correct 1 ms 1104 KB Output is correct
101 Correct 2 ms 1056 KB Output is correct
102 Correct 30 ms 1872 KB Output is correct
103 Correct 3 ms 1616 KB Output is correct
104 Correct 8 ms 1612 KB Output is correct
105 Correct 1 ms 592 KB Output is correct
106 Correct 14 ms 1624 KB Output is correct
107 Correct 16 ms 2136 KB Output is correct