Submission #828042

#	Time	Username	Problem	Language	Result	Execution time	Memory
828042		resting	Viruses (BOI20_viruses)	C++17	100 / 100	561 ms	70372 KiB

Viruses

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'


bool contains(vector<int> a, vector<int> b) {
    for (int i = 0; i + a.size() <= b.size(); i++) {
        bool ye = true;
        for (int j = 0; j < a.size(); j++) {
            if (a[j] != b[i + j]) ye = false;
        }
        if (ye) return true;
    }
    return false;
}

int ans[105][55][55]{}; // visited ({index, input, output}) to avoid too much bad stuff from happening
int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int G, N, M; cin >> G >> N >> M;

    vector<pair<int, int>> left[105]; // should be 105 "types" max, user is on the right
    vector<pair<int, int>> right[105]; // should be 105 "types" max, user is on the left, but thing is on the right ykyk

    int extra = G;
    for (int i = 0; i < N; i++) {
        int key; cin >> key;
        int t; cin >> t;
        int pre; cin >> pre;
        for (int j = 1; j < t - 1; j++) {
            int cur; cin >> cur;

            left[cur].push_back({ pre, extra });
            right[pre].push_back({ cur, extra });
            pre = extra++;
            // fut = {pre, cur}
            // pre = fut
        }
        if (t == 1) {
            int cur = 104;
            left[cur].push_back({ pre, key });
            right[pre].push_back({ cur, key });
        } else {
            int cur; cin >> cur;
            left[cur].push_back({ pre, key });
            right[pre].push_back({ cur, key });
        }
    }


    vector<vector<int>> anti(M);
    for (auto& x : anti) {
        int t; cin >> t;
        //cout << "A" << t << endl;
        x = vector<int>(t);
        for (auto& x : x) cin >> x;
    }

    map<vector<int>, int> pre;
    pre[{}]++;
    for (auto& x : anti) {
        vector<int> cur; pre[cur]++;
        for (auto& i : x) {
            cur.push_back(i);
            pre[cur]++;
        }
    }
    int sz = 0;
    for (auto& x : pre) x.second = sz++;



    //vis
    set<pair<pair<int, int>, pair<int, int>>> q; // {length, index, input/output}

    for (int i = 0; i < 2; i++) {
        for (auto& x : pre) {
            //for (auto& i : x.first)cout << i << ",";
            //cout << endl;
            vector<int> sigh = x.first;
            sigh.push_back(i);
            //check if bad
            for (auto& y : anti) {
                if (contains(y, sigh)) {
                    // cout << "BAD" << endl;
                    // for (auto& x : sigh)cout << x;
                    // cout << endl;
                    // for (auto& x : y) cout << x;
                    // cout << endl;
                    goto bad;
                }
            }
            //cout << "not bad!" << endl;
            //get prefix
            while (!pre.count(sigh))sigh.erase(sigh.begin());
            q.insert(pair<pair<int, int>, pair<int, int>>({ {1, i}, { x.second, pre[sigh] } }));
        bad:;
        }
    }

    while (q.size()) {
        auto v = *q.begin(); q.erase(q.begin());
        if (ans[v.first.second][v.second.first][v.second.second]) continue;
        //cout << v.first.second << "," << v.second.first << "," << v.second.second << "," << v.first.first << endl;
        ans[v.first.second][v.second.first][v.second.second] = v.first.first;
        //cout << v.first << "," << v.second.first << "," << v.second.second << "," << ans[v.first][v.second.first][v.second.second] << endl;
        for (auto& x : left[v.first.second]) {
            //cout << "!" << x.second << endl;
            for (int j = 0; j < sz; j++) {
                if ((x.first == 104 && j == v.second.first) || ans[x.first][j][v.second.first]) {
                    if (!ans[x.second][j][v.second.second])
                        q.insert(pair<pair<int, int>, pair<int, int>>({ {ans[x.first][j][v.second.first] + ans[v.first.second][v.second.first][v.second.second], x.second}, { j, v.second.second } }));
                }
            }
        }

        for (auto& x : right[v.first.second]) {
            for (int j = 0; j < sz; j++) {
                if ((x.first == 104 && j == v.second.second) || ans[x.first][v.second.second][j]) {
                    if (!ans[x.second][v.second.first][j])
                        q.insert(pair<pair<int, int>, pair<int, int>>({ {ans[x.first][v.second.second][j] + ans[v.first.second][v.second.first][v.second.second], x.second}, { v.second.first, j } }));
                }
            }
        }

    }
    for (int i = 2; i < G; i++) {
        int res = numeric_limits<int>::max();
        for (int x = 0; x < sz; x++) {
            for (int y = 0; y < sz; y++) {
                if (ans[i][x][y]) {
                    res = min(res, ans[i][x][y]);
                }
            }
        }
        if (res == numeric_limits<int>::max())cout << "YES" << endl;
        else cout << "NO " << res << endl;
    }
}

Compilation message (stderr)

Viruses.cpp: In function 'bool contains(std::vector<long long int>, std::vector<long long int>)':
Viruses.cpp:11:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |         for (int j = 0; j < a.size(); j++) {
      |                         ~~^~~~~~~~~~

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