oj.uz

Submission #828048

# Submission time Handle Problem Language Result Execution time Memory
828048 2023-08-17T02:35:35 Z resting Viruses (BOI20_viruses) C++17
100 / 100
 41 ms 4088 KB 
#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
int vis[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 (vis[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;
        vis[v.first.second][v.second.first][v.second.second] = 1;
        //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) || vis[x.first][j][v.second.first]) {
                    if (!ans[x.second][j][v.second.second] || ans[x.first][j][v.second.first] + ans[v.first.second][v.second.first][v.second.second] < ans[x.second][j][v.second.second]) {
                        ans[x.second][j][v.second.second] = ans[x.first][j][v.second.first] + ans[v.first.second][v.second.first][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) || vis[x.first][v.second.second][j]) {
                    if (!ans[x.second][v.second.first][j] || ans[x.first][v.second.second][j] + ans[v.first.second][v.second.first][v.second.second] < ans[x.second][v.second.first][j]) {
                        ans[x.second][v.second.first][j] = ans[x.first][v.second.second][j] + ans[v.first.second][v.second.first][v.second.second];
                        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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 0 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 0 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 724 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 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 352 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 2 ms 1876 KB Output is correct
7 Correct 2 ms 2260 KB Output is correct
8 Correct 2 ms 2516 KB Output is correct
9 Correct 2 ms 1620 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 1108 KB Output is correct
14 Correct 1 ms 980 KB Output is correct
15 Correct 1 ms 1364 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 980 KB Output is correct
18 Correct 1 ms 980 KB Output is correct
19 Correct 1 ms 1236 KB Output is correct
20 Correct 1 ms 1364 KB Output is correct
21 Correct 1 ms 1108 KB Output is correct
22 Correct 1 ms 852 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 2 ms 1876 KB Output is correct
4 Correct 2 ms 1876 KB Output is correct
5 Correct 2 ms 2260 KB Output is correct
6 Correct 2 ms 2516 KB Output is correct
7 Correct 2 ms 1620 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 0 ms 416 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 480 KB Output is correct
13 Correct 0 ms 468 KB Output is correct
14 Correct 0 ms 468 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 852 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 1 ms 724 KB Output is correct
21 Correct 0 ms 596 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 596 KB Output is correct
24 Correct 1 ms 852 KB Output is correct
25 Correct 3 ms 1748 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 41 ms 2996 KB Output is correct
28 Correct 4 ms 3540 KB Output is correct
29 Correct 33 ms 2388 KB Output is correct
30 Correct 39 ms 2132 KB Output is correct
31 Correct 6 ms 3540 KB Output is correct
32 Correct 4 ms 3668 KB Output is correct
33 Correct 2 ms 2644 KB Output is correct
34 Correct 34 ms 2132 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 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 0 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 0 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 724 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 0 ms 416 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 0 ms 480 KB Output is correct
27 Correct 0 ms 468 KB Output is correct
28 Correct 0 ms 468 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 1 ms 852 KB Output is correct
33 Correct 1 ms 596 KB Output is correct
34 Correct 1 ms 724 KB Output is correct
35 Correct 0 ms 596 KB Output is correct
36 Correct 1 ms 468 KB Output is correct
37 Correct 1 ms 596 KB Output is correct
38 Correct 1 ms 852 KB Output is correct
39 Correct 0 ms 340 KB Output is correct
40 Correct 1 ms 724 KB Output is correct
41 Correct 0 ms 340 KB Output is correct
42 Correct 0 ms 212 KB Output is correct
43 Correct 0 ms 468 KB Output is correct
44 Correct 1 ms 724 KB Output is correct
45 Correct 0 ms 468 KB Output is correct
46 Correct 0 ms 468 KB Output is correct
47 Correct 0 ms 468 KB Output is correct
48 Correct 1 ms 1108 KB Output is correct
49 Correct 1 ms 596 KB Output is correct
50 Correct 1 ms 468 KB Output is correct
51 Correct 1 ms 596 KB Output is correct
52 Correct 1 ms 1108 KB Output is correct
53 Correct 1 ms 596 KB Output is correct
54 Correct 1 ms 1236 KB Output is correct
55 Correct 1 ms 852 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 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 0 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 852 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct
16 Correct 1 ms 724 KB Output is correct
17 Correct 0 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 724 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 352 KB Output is correct
23 Correct 2 ms 1876 KB Output is correct
24 Correct 2 ms 1876 KB Output is correct
25 Correct 2 ms 2260 KB Output is correct
26 Correct 2 ms 2516 KB Output is correct
27 Correct 2 ms 1620 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Correct 1 ms 852 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 1 ms 1108 KB Output is correct
32 Correct 1 ms 980 KB Output is correct
33 Correct 1 ms 1364 KB Output is correct
34 Correct 1 ms 596 KB Output is correct
35 Correct 1 ms 980 KB Output is correct
36 Correct 1 ms 980 KB Output is correct
37 Correct 1 ms 1236 KB Output is correct
38 Correct 1 ms 1364 KB Output is correct
39 Correct 1 ms 1108 KB Output is correct
40 Correct 1 ms 852 KB Output is correct
41 Correct 0 ms 340 KB Output is correct
42 Correct 0 ms 340 KB Output is correct
43 Correct 1 ms 596 KB Output is correct
44 Correct 0 ms 416 KB Output is correct
45 Correct 1 ms 468 KB Output is correct
46 Correct 0 ms 340 KB Output is correct
47 Correct 0 ms 480 KB Output is correct
48 Correct 0 ms 468 KB Output is correct
49 Correct 0 ms 468 KB Output is correct
50 Correct 1 ms 340 KB Output is correct
51 Correct 0 ms 340 KB Output is correct
52 Correct 0 ms 340 KB Output is correct
53 Correct 1 ms 852 KB Output is correct
54 Correct 1 ms 596 KB Output is correct
55 Correct 1 ms 724 KB Output is correct
56 Correct 0 ms 596 KB Output is correct
57 Correct 1 ms 468 KB Output is correct
58 Correct 1 ms 596 KB Output is correct
59 Correct 1 ms 852 KB Output is correct
60 Correct 3 ms 1748 KB Output is correct
61 Correct 1 ms 468 KB Output is correct
62 Correct 41 ms 2996 KB Output is correct
63 Correct 4 ms 3540 KB Output is correct
64 Correct 33 ms 2388 KB Output is correct
65 Correct 39 ms 2132 KB Output is correct
66 Correct 6 ms 3540 KB Output is correct
67 Correct 4 ms 3668 KB Output is correct
68 Correct 2 ms 2644 KB Output is correct
69 Correct 34 ms 2132 KB Output is correct
70 Correct 0 ms 340 KB Output is correct
71 Correct 1 ms 724 KB Output is correct
72 Correct 0 ms 340 KB Output is correct
73 Correct 0 ms 212 KB Output is correct
74 Correct 0 ms 468 KB Output is correct
75 Correct 1 ms 724 KB Output is correct
76 Correct 0 ms 468 KB Output is correct
77 Correct 0 ms 468 KB Output is correct
78 Correct 0 ms 468 KB Output is correct
79 Correct 1 ms 1108 KB Output is correct
80 Correct 1 ms 596 KB Output is correct
81 Correct 1 ms 468 KB Output is correct
82 Correct 1 ms 596 KB Output is correct
83 Correct 1 ms 1108 KB Output is correct
84 Correct 1 ms 596 KB Output is correct
85 Correct 1 ms 1236 KB Output is correct
86 Correct 1 ms 852 KB Output is correct
87 Correct 5 ms 1768 KB Output is correct
88 Correct 0 ms 340 KB Output is correct
89 Correct 0 ms 468 KB Output is correct
90 Correct 1 ms 596 KB Output is correct
91 Correct 1 ms 724 KB Output is correct
92 Correct 20 ms 4088 KB Output is correct
93 Correct 13 ms 3340 KB Output is correct
94 Correct 1 ms 1280 KB Output is correct
95 Correct 1 ms 724 KB Output is correct
96 Correct 1 ms 852 KB Output is correct
97 Correct 5 ms 2604 KB Output is correct
98 Correct 1 ms 1236 KB Output is correct
99 Correct 7 ms 3156 KB Output is correct
100 Correct 1 ms 1236 KB Output is correct
101 Correct 3 ms 2388 KB Output is correct
102 Correct 37 ms 4052 KB Output is correct
103 Correct 3 ms 3284 KB Output is correct
104 Correct 10 ms 3376 KB Output is correct
105 Correct 1 ms 980 KB Output is correct
106 Correct 18 ms 3560 KB Output is correct
107 Correct 17 ms 3468 KB Output is correct