| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 625178 |
2022-08-09T14:27:39 Z |
KoD |
Viruses (BOI20_viruses) |
C++17 |
|
700 ms |
468 KB |
#include <bits/stdc++.h>
using ull = unsigned long long;
using std::vector;
using std::array;
using std::pair;
template <class T>
bool setmin(T& x, const T& y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template <class T>
using min_heap = std::priority_queue<T, vector<T>, std::greater<>>;
class Trie {
struct Node {
array<int, 2> next;
int link;
bool bad;
Node() : next({-1, -1}), link(-1), bad(false) {}
};
vector<Node> node;
public:
Trie() : node({Node()}) {}
void insert(const vector<int>& str) {
int u = 0;
for (const int x : str) {
if (node[u].next[x] == -1) {
node[u].next[x] = node.size();
node.emplace_back();
}
u = node[u].next[x];
}
node[u].bad = true;
}
vector<array<int, 3>> build() {
std::queue<int> que;
for (const int k : {0, 1}) {
if (node[0].next[k] == -1) {
node[0].next[k] = node.size();
}
const int u = node[0].next[k];
node[u].link = 0;
que.push(u);
}
while (!que.empty()) {
const int u = que.front();
que.pop();
for (const int k : {0, 1}) {
const int v = node[u].next[k];
if (v == -1) {
continue;
}
que.push(v);
int t = u;
do {
t = node[t].link;
} while (node[t].next[k] == -1);
const int s = node[t].next[k];
node[v].link = s;
if (node[s].bad) {
node[v].bad = true;
}
}
}
const int V = node.size();
vector<array<int, 3>> ret(V);
for (int u = 0; u < V; ++u) {
for (const int k : {0, 1}) {
int v = u;
while (node[v].next[k] == -1) {
v = node[v].link;
}
ret[u][k] = node[v].next[k];
}
ret[u][2] = node[u].bad;
}
return ret;
}
};
struct State {
ull d;
int i, j, u, v;
bool operator<(const State& other) const { return d < other.d; }
bool operator>(const State& other) const { return d > other.d; }
};
constexpr ull inf = std::numeric_limits<ull>::max();
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int G, N, K;
std::cin >> G >> N >> K;
vector<int> id(N);
vector<vector<int>> seq(N);
for (int i = 0; i < N; ++i) {
int k;
std::cin >> id[i] >> k;
seq[i].resize(k);
for (auto& x : seq[i]) {
std::cin >> x;
}
}
Trie trie;
while (K--) {
int k;
std::cin >> k;
vector<int> str(k);
for (auto& x : str) {
std::cin >> x;
}
trie.insert(str);
}
const auto data = trie.build();
const int V = data.size();
vector complete(G, vector(V, vector(V, inf)));
vector<vector<vector<vector<ull>>>> make(N);
for (int i = 0; i < N; ++i) {
make[i] = vector(seq[i].size() + 1, vector(V, vector(V, inf)));
}
min_heap<State> heap;
const auto push_c = [&](const int i, const int u, const int v, const ull d) {
if (!data[u][2] and !data[v][2] and setmin(complete[i][u][v], d)) {
heap.push({d, i, -1, u, v});
}
};
const auto push_m = [&](const int i, const int j, const int u, const int v, const ull d) {
if (!data[u][2] and !data[v][2] and setmin(make[i][j][u][v], d)) {
heap.push({d, i, j, u, v});
}
};
for (const int k : {0, 1}) {
for (int i = 0; i < V; ++i) {
const int j = data[i][k];
push_c(k, i, j, 1);
}
}
for (int i = 0; i < N; ++i) {
for (int u = 0; u < V; ++u) {
push_m(i, 0, u, u, 0);
}
}
while (!heap.empty()) {
const auto [d, i, j, u, v] = heap.top();
heap.pop();
if (j == -1) {
if (d > complete[i][u][v]) {
continue;
}
for (int k = 0; k < N; ++k) {
for (int l = 0; l < (int)seq[k].size(); ++l) {
if (seq[k][l] == i) {
for (int m = 0; m < V; ++m) {
if (const ull tmp = make[k][l][m][u]; tmp != inf) {
push_m(k, l + 1, m, v, tmp + d);
}
}
}
}
}
} else if (j == (int)seq[i].size()) {
push_c(id[i], u, v, d);
} else {
if (d > make[i][j][u][v]) {
continue;
}
const int k = seq[i][j];
for (int l = 0; l < V; ++l) {
if (const ull tmp = complete[k][v][l]; tmp != inf) {
push_m(i, j + 1, u, l, d + tmp);
}
}
}
}
for (int i = 2; i < G; ++i) {
ull min = inf;
for (int u = 0; u < V; ++u) {
setmin(min, complete[i][0][u]);
}
if (min == inf) {
std::cout << "YES\n";
} else {
std::cout << "NO " << min << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1090 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
