Submission #828044

#TimeUsernameProblemLanguageResultExecution timeMemory
828044restingViruses (BOI20_viruses)C++17
0 / 100
1 ms468 KiB
#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] || 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) || ans[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 (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++) {
      |                         ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...