#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 (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;
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++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
