Submission #828020

#	Time	Username	Problem	Language	Result	Execution time	Memory
828020		resting	Viruses (BOI20_viruses)	C++17	0 / 100	25 ms	1620 KiB

Viruses

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

#define int long long


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() {
    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 = N;
    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;
    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
    vector<pair<int, pair<int, int>>> q; // {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.push_back({ i, {x.second, pre[sigh]} });
            ans[i][x.second][pre[sigh]] = 1;
        bad:;
        }
    }

    while (q.size()) {
        auto v = q.back(); q.pop_back();
        //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]) {
            //cout << "!" << x.second << endl;
            for (int j = 0; j < sz; j++) {
                if (x.first == 104 || ans[x.first][j][v.second.first]) {
                    if (!ans[x.second][j][v.second.second]) {
                        ans[x.second][j][v.second.second] = ans[x.first][j][v.second.first] + ans[v.first][v.second.first][v.second.second];
                        q.push_back({ x.second, {j, v.second.second} });
                    }
                }
            }
        }

        for (auto& x : right[v.first]) {
            for (int j = 0; j < sz; j++) {
                if (x.first == 104 || ans[x.first][v.second.second][j]) {
                    if (!ans[x.second][v.second.first][j]) {
                        ans[x.second][v.second.first][j] = ans[x.first][v.second.second][j] + ans[v.first][v.second.first][v.second.second];
                        q.push_back({ 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:10: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]
   10 |         for (int j = 0; j < a.size(); j++) {
      |                         ~~^~~~~~~~~~

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