oj.uz

Submission #828039

# Submission time Handle Problem Language Result Execution time Memory
828039 2023-08-17T02:20:21 Z resting Viruses (BOI20_viruses) C++17
57 / 100
 700 ms 86628 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
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]) {
                    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]) {
                    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 212 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 0 ms 468 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 0 ms 468 KB Output is correct
17 Correct 0 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 1 ms 1108 KB Output is correct
6 Correct 1 ms 1108 KB Output is correct
7 Correct 2 ms 1236 KB Output is correct
8 Correct 2 ms 1492 KB Output is correct
9 Correct 1 ms 980 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 852 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 736 KB Output is correct
20 Correct 1 ms 852 KB Output is correct
21 Correct 1 ms 724 KB Output is correct
22 Correct 1 ms 600 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 1108 KB Output is correct
4 Correct 1 ms 1108 KB Output is correct
5 Correct 2 ms 1236 KB Output is correct
6 Correct 2 ms 1492 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 1 ms 464 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 468 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 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 2 ms 596 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 0 ms 468 KB Output is correct
21 Correct 0 ms 468 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 596 KB Output is correct
25 Correct 3 ms 1108 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 362 ms 1668 KB Output is correct
28 Correct 3 ms 2004 KB Output is correct
29 Execution timed out 1020 ms 86628 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 0 ms 468 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 0 ms 468 KB Output is correct
17 Correct 0 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 464 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 468 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Correct 0 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 2 ms 596 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Correct 0 ms 468 KB Output is correct
35 Correct 0 ms 468 KB Output is correct
36 Correct 0 ms 340 KB Output is correct
37 Correct 1 ms 468 KB Output is correct
38 Correct 1 ms 596 KB Output is correct
39 Correct 0 ms 340 KB Output is correct
40 Correct 1 ms 468 KB Output is correct
41 Correct 0 ms 340 KB Output is correct
42 Correct 1 ms 340 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 1 ms 468 KB Output is correct
45 Correct 1 ms 340 KB Output is correct
46 Correct 1 ms 468 KB Output is correct
47 Correct 1 ms 340 KB Output is correct
48 Correct 2 ms 724 KB Output is correct
49 Correct 1 ms 468 KB Output is correct
50 Correct 0 ms 340 KB Output is correct
51 Correct 0 ms 468 KB Output is correct
52 Correct 2 ms 852 KB Output is correct
53 Correct 1 ms 468 KB Output is correct
54 Correct 1 ms 720 KB Output is correct
55 Correct 1 ms 596 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 0 ms 468 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 0 ms 468 KB Output is correct
17 Correct 0 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 1 ms 1108 KB Output is correct
24 Correct 1 ms 1108 KB Output is correct
25 Correct 2 ms 1236 KB Output is correct
26 Correct 2 ms 1492 KB Output is correct
27 Correct 1 ms 980 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 596 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 724 KB Output is correct
32 Correct 1 ms 596 KB Output is correct
33 Correct 1 ms 852 KB Output is correct
34 Correct 1 ms 468 KB Output is correct
35 Correct 1 ms 596 KB Output is correct
36 Correct 1 ms 596 KB Output is correct
37 Correct 1 ms 736 KB Output is correct
38 Correct 1 ms 852 KB Output is correct
39 Correct 1 ms 724 KB Output is correct
40 Correct 1 ms 600 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 0 ms 340 KB Output is correct
43 Correct 1 ms 464 KB Output is correct
44 Correct 0 ms 340 KB Output is correct
45 Correct 1 ms 340 KB Output is correct
46 Correct 1 ms 340 KB Output is correct
47 Correct 0 ms 340 KB Output is correct
48 Correct 0 ms 468 KB Output is correct
49 Correct 0 ms 340 KB Output is correct
50 Correct 0 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 2 ms 596 KB Output is correct
54 Correct 1 ms 468 KB Output is correct
55 Correct 0 ms 468 KB Output is correct
56 Correct 0 ms 468 KB Output is correct
57 Correct 0 ms 340 KB Output is correct
58 Correct 1 ms 468 KB Output is correct
59 Correct 1 ms 596 KB Output is correct
60 Correct 3 ms 1108 KB Output is correct
61 Correct 1 ms 340 KB Output is correct
62 Correct 362 ms 1668 KB Output is correct
63 Correct 3 ms 2004 KB Output is correct
64 Execution timed out 1020 ms 86628 KB Time limit exceeded
65 Halted 0 ms 0 KB -