Submission #1110756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110756		Zero_OP	Viruses (BOI20_viruses)	C++14	0 / 100	1 ms	336 KiB

Viruses

#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for(int i = (l); i < (r); ++i)
#define sz(v) (int)v.size()
#define dbg(x) "[" #x " = " << (x) << "]"
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define file(name) if(fopen(name".inp", "r")){ freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

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

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;

template<int ALPHABET = 26>
struct AhoCorasick{
    static const int C = ALPHABET;
    struct Node{
        int link, next[C]; bool v;
        Node(){
            link = -1;
            v = false;
            memset(next, -1, sizeof(next));
        }
    };

    vector<Node> Nodes;
    AhoCorasick() : Nodes(){
        Nodes.emplace_back();
    }

    int size(){ return sz(Nodes); }
    int go(int u, int c){ return Nodes[u].next[c]; }
    int link(int u){ return Nodes[u].link; }

    void addString(const vector<int>& s){
        int u = 0;
        for(auto c : s){
            if(Nodes[u].next[c] == -1){
                Nodes[u].next[c] = size();
                Nodes.emplace_back();
            }
            u = Nodes[u].next[c];
        }
        Nodes[u].v = true;
    }

    void build_links(){
        queue<int> q;
        q.push(0);
        while(!q.empty()){
            int u = q.front(), link = Nodes[u].link; q.pop();
            if(u > 0) Nodes[u].v |= Nodes[link].v;
            for(int c = 0; c < C; ++c){
                int& nxt = Nodes[u].next[c], nxt_link = (u ? Nodes[link].next[c] : 0);
                if(nxt == -1) nxt = nxt_link;
                else{
                    Nodes[nxt].next[c] = nxt_link;
                    q.push(nxt);
                }
            }
        }
    }

    bool check(int u){ return !Nodes[u].v; }
};

const ull inf = (1ULL << 63);

ull add(ull a, ull b){
    if(a == inf || b == inf) return inf;
    return a + b;
}

void upd(ull& a, ull b){
    if(a == inf || b == inf) a = inf;
    else a += b;
}

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

    int G, N, M;
    cin >> G >> N >> M;

    vector<vector<int>> mutations(N);
    vector<vector<int>> options(G);

    for(int i = 0; i < N; ++i){
        int a, k;
        cin >> a >> k;
        options[a].emplace_back(i);
        for(int j = 0; j < k; ++j){
            int b; cin >> b;
            mutations[i].emplace_back(b);
        }
    }

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

    if(M == 0){
        vector<ull> dp(G, inf);
        dp[0] = dp[1] = 1;

        for(int turn = 0; turn < N; ++turn){
            for(int a = 0; a < G; ++a){
                for(auto id_mutation : options[a]){
                    ull res = 0;
                    for(auto b : mutations[id_mutation]){
                        upd(res, dp[b]);
                    }

                    minimize(dp[a], res);
                }
            }
        }

        for(int i = 2; i < G; ++i){
            if(dp[i] == inf) cout << "Yes\n";
            else cout << "No " << dp[i] << '\n';
        }
    }

    return 0;
}

/*

Testcase
subtask 1 :
5 6 0
2 2 1 0
2 2 3 2
3 1 4
4 2 3 2
4 2 0 0
3 2 1 1

answer : 
No 2
No 2
No 2

*/

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 32
• Subtask 5: 0 / 18