QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#404433#5707. Viruseszhaohaikun0 2ms16324kbC++206.3kb2024-05-03 22:22:032024-05-03 22:22:17

Judging History

你现在查看的是最新测评结果

  • [2024-05-03 22:22:17]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:16324kb
  • [2024-05-03 22:22:03]
  • 提交

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%