QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#404433 | #5707. Viruses | zhaohaikun | 0 | 2ms | 16324kb | C++20 | 6.3kb | 2024-05-03 22:22:03 | 2024-05-03 22:22:17 |
Judging History
answer
// MagicDark
#include <bits/stdc++.h>
#define debug cerr << "\033[32m[" << __LINE__ << "]\033[0m "
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);}
// template <typename T> T& read(T &x) {
// x = 0; int f = 1; char c = getchar();
// for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
// for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
// return x *= f;
// }
const int N = 110, M = 5010;
int sg, n, m, x[N], y[N], t[N][N], s[N];
//, tpre, tsuf;
ull f[N][M], g[N][M];
bool visf[N][M], visg[N][M];
// unordered_map <string, bool> mp1;
// unordered_map <string, int> mp2;
// unordered_map <string, int> mppre;
// unordered_map <string, int> mpsuf;
// string stpre[N], stsuf[N];
struct DS {
// int tot;
unordered_map <string, int> mp;
// string st[N];
vector <string> st;
// DS() {
// mp[""] = 0;
// st.push_back("");
// }
void ins(string tt) {
if (mp.count(tt)) return;
mp[tt] = st.size();
st.push_back(tt);
}
int query(string st) {
if (mp.count(st)) return mp[st];
return -1;
}
int size() {
return st.size();
}
} pre, suf, h, ban;
bool check(string st) {
F(l, 0, SZ(st)) {
string s = "";
F(r, l, SZ(st)) {
s += st[r];
if (~ban.query(s)) return false;
}
}
return true;
}
int q1(string st) {
// if (!check(st)) return -1;
DF(i, st.size(), 1) {
string s = st.substr(0, i);
int ans = suf.query(s);
if (~ans) return ans;
}
return 0;
}
int q2(string st) {
// if (!check(st)) return -1;
DF(i, st.size(), 1) {
string s = st.substr(st.size() - i, i);
// debug << st << " " << s << endl;
int ans = pre.query(s);
if (~ans) return ans;
}
return 0;
}
int encode(int x, int y) {
return h.size() + x * pre.size() + y;
}
pair <int, int> decode(int x) {
x -= h.st.size();
// debug << x << " " << x / pre.st.size() << ' ' << x % pre.st.size() << endl;
return make_pair(x / pre.size(), x % pre.size());
}
int calc(string st) {
if (!check(st)) return -1;
int ans = h.query(st);
if (~ans) return ans;
return encode(q1(st), q2(st));
}
int tot, tt[M][M];
int trans(int x, int y) {
if (x < h.size()) {
if (y < h.st.size()) return calc(h.st[x] + h.st[y]);
pair <int, int> ty = decode(y);
if (!check(h.st[x] + suf.st[ty.first])) return -1;
return encode(q1(h.st[x] + suf.st[ty.first]), ty.second);
}
pair <int, int> tx = decode(x);
if (y < h.st.size()) {
if (!check(pre.st[tx.second] + h.st[y])) return -1;
return encode(tx.first, q2(pre.st[tx.second] + h.st[y]));
}
pair <int, int> ty = decode(y);
if (!check(pre.st[tx.second] + suf.st[ty.first])) return -1;
return encode(tx.first, ty.second);
}
vector <int> p[N];
pair <int, int> u[N];
signed main() {
cin.tie(0) -> sync_with_stdio(0); // don't use puts
cin >> sg >> n >> m;
ms(f, 127), ms(g, 127);
ull inf = f[0][0];
// debug << inf << endl;
// debug << (1ull << 63) << endl;
F(i, 1, n) {
cin >> x[i] >> y[i];
s[i] = s[i - 1] + y[i] + 1;
F(j, 1, y[i]) {
cin >> t[i][j];
u[s[i - 1] + j] = make_pair(i, j);
p[t[i][j]].push_back(s[i - 1] + j);
}
}
pre.ins(""), suf.ins("");
F(i, 1, m) {
int k;
cin >> k;
string st = "";
F(j, 1, k) {
char c;
cin >> c;
st += c;
}
{
string s = "";
F(j, 0, SZ(st)) pre.ins(s += st[j]);
}
{
string s = "";
DF(j, SZ(st), 0) suf.ins(s += st[j]);
}
{
F(l, 0, SZ(st)) {
string s = "";
F(r, l, SZ(st)) {
s += st[r];
h.ins(s);
}
}
}
ban.ins(st);
// debug << st << endl;
}
// F(i, 1, n) g[s[i - 1]][h.size()] = 0, visg[s[i - 1]][h.size()] = true;
tot = h.size() - 1 + suf.st.size() * pre.st.size();
// debug << decode(tot).first << " " << decode(tot).second << endl;
F(i, 0, tot)
F(j, 0, tot)
tt[i][j] = trans(i, j);
priority_queue <pair <ll, pair <int, int>>, vector <pair <ll, pair <int, int>>>, greater <pair <ll, pair <int, int>>>> q;
{
int w = calc("0");
// debug << w << endl;
if (~w) q.emplace(f[0][w] = 1, make_pair(0, w));
}
{
int w = calc("1");
// debug << w << endl;
if (~w) q.emplace(f[1][w] = 1, make_pair(1, w));
}
// debug << pre.size() << " " << suf.size() << endl;
// debug << tt[][21] << endl;
// debug << h.size() << endl;
// debug << tt[h.size()][0] << endl;
while (q.size()) {
auto [x, y] = q.top().second; q.pop();
if (x >= 0) {
if (visf[x][y]) continue;
visf[x][y] = true;
// debug << x << " " << y << " " << f[x][y] << endl;
// if (y >= h.size()) {
// auto [a, b] = decode(y);
// debug << a << ' ' << b << " " << suf.st[a] << " " << pre.st[b] << endl;
// } else {
// debug << h.st[y] << endl;
// }
for (int j: p[x]) {
if (u[j].second == 1) {
q.emplace(g[j][y] = f[x][y], make_pair(- j, y));
continue;
}
F(t, 0, tot) {
if ((~tt[t][y]) && visg[j - 1][t] && g[j - 1][t] + f[x][y] < g[j][tt[t][y]])
q.emplace(g[j][tt[t][y]] = g[j - 1][t] + f[x][y], make_pair(- j, tt[t][y]));//, debug << "~ " << tt[t][y] << endl;
}
}
} else {
x *= -1;
if (visg[x][y]) continue;
visg[x][y] = true;
auto [a, b] = u[x];
// debug << a << ' ' << b << ' ' << y << " " << g[x][y] << endl;
// debug << " -> " << ::y[a] << endl;
// if (y >= h.size()) {
// auto [a, b] = decode(y);
// debug << a << ' ' << b << " " << suf.st[a] << " " << pre.st[b] << endl;
// } else {
// debug << h.st[y] << endl;
// }
if (b == ::y[a]) {
if (g[x][y] < f[::x[a]][y]) q.emplace(f[::x[a]][y] = g[x][y], make_pair(::x[a], y));
} else {
F(t, 0, tot) {
if ((~tt[y][t]) && visf[::t[a][b + 1]][t] && g[x][y] + f[::t[a][b + 1]][t] < g[x + 1][tt[y][t]])
q.emplace(g[x + 1][tt[y][t]] = g[x][y] + f[::t[a][b + 1]][t], make_pair(- (x + 1), tt[y][t]));
}
}
}
}
F(i, 2, sg - 1) {
ull ans = inf;
F(j, 0, tot) chkmin(ans, f[i][j]);
if (ans != inf) cout << "NO " << ans << '\n';
else cout << "YES\n";
}
return 0;
}
/* why?
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
35 66 0 2 2 1 1 2 1 2 3 2 2 2 3 1 3 4 2 3 3 4 1 4 5 2 4 4 5 1 5 6 2 5 5 6 1 6 7 2 6 6 7 1 7 8 2 7 7 8 1 8 9 2 8 8 9 1 9 10 2 9 9 10 1 10 11 2 10 10 11 1 11 12 2 11 11 12 1 12 13 2 12 12 13 1 13 14 2 13 13 14 1 14 15 2 14 14 15 1 15 16 2 15 15 16 1 16 17 2 16 16 17 1 17 18 2 17 17 18 1 18 19 2 18 18 ...
output:
result:
Subtask #2:
score: 0
Time Limit Exceeded
Test #21:
score: 0
Time Limit Exceeded
input:
52 50 1 2 2 1 1 3 2 2 2 4 2 3 3 5 2 4 4 6 2 5 5 7 2 6 6 8 2 7 7 9 2 8 8 10 2 9 9 11 2 10 10 12 2 11 11 13 2 12 12 14 2 13 13 15 2 14 14 16 2 15 15 17 2 16 16 18 2 17 17 19 2 18 18 20 2 19 19 21 2 20 20 22 2 21 21 23 2 22 22 24 2 23 23 25 2 24 24 26 2 25 25 27 2 26 26 28 2 27 27 29 2 28 28 30 2 29 29...
output:
result:
Subtask #3:
score: 0
Runtime Error
Test #43:
score: 0
Runtime Error
input:
22 40 1 2 3 1 1 1 2 2 0 1 3 3 1 2 2 3 2 0 2 4 3 1 3 3 4 2 0 3 5 3 1 4 4 5 2 0 4 6 3 1 5 5 6 2 0 5 7 3 1 6 6 7 2 0 6 8 3 1 7 7 8 2 0 7 9 3 1 8 8 9 2 0 8 10 3 1 9 9 10 2 0 9 11 3 1 10 10 11 2 0 10 12 3 1 11 11 12 2 0 11 13 3 1 12 12 13 2 0 12 14 3 1 13 13 14 2 0 13 15 3 1 14 14 15 2 0 14 16 3 1 15 15 ...
output:
result:
Subtask #4:
score: 0
Runtime Error
Test #70:
score: 32
Accepted
time: 2ms
memory: 16324kb
input:
6 6 2 2 2 0 1 3 3 2 0 0 3 2 1 3 4 4 0 3 1 2 5 2 2 1 5 1 5 2 1 1 5 0 0 1 0 0
output:
NO 2 NO 4 NO 9 YES
result:
ok 4 lines
Test #71:
score: 0
Runtime Error
input:
22 40 2 2 2 0 1 2 2 1 0 3 3 1 2 2 3 2 0 2 4 3 1 3 3 4 2 0 3 5 3 1 4 4 5 2 0 4 6 3 1 5 5 6 2 0 5 7 3 1 6 6 7 2 0 6 8 3 1 7 7 8 2 0 7 9 3 1 8 8 9 2 0 8 10 3 1 9 9 10 2 0 9 11 3 1 10 10 11 2 0 10 12 3 1 11 11 12 2 0 11 13 3 1 12 12 13 2 0 12 14 3 1 13 13 14 2 0 13 15 3 1 14 14 15 2 0 14 16 3 1 15 15 16...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
0%