QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#404568#5707. Viruseszhaohaikun0 0ms0kbC++205.0kb2024-05-04 08:53:052024-05-04 08:53:05

Judging History

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

  • [2024-05-04 08:53:05]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-05-04 08:53:05]
  • 提交

answer

#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
// 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 = 55;
int sg, n, m, x[N], y[N], t[N][N], s[N];
vector <int> p[N];
pair <int, int> u[N];
string o[N];
struct ACAM {
	int son[N][2], tot, link[N];
	bool vis[N];
	int ins(int num, int f) {
		if (!son[num][f]) son[num][f] = ++tot;
		return son[num][f];
	}
	void build() {
		queue <int> q;
		F(i, 0, 1)
			if (son[0][i]) q.push(son[0][i]);
		while (q.size()) {
			int x = q.front(); q.pop();
			F(i, 0, 1)
				if (son[x][i]) {
					link[son[x][i]] = son[link[x]][i];
					q.push(son[x][i]);
				} else son[x][i] = son[link[x]][i];
		}
	}
} AC;
ull f[N][M][M], g[N][M][M];
bool visf[N][M][M], visg[N][M][M];
signed main() {
	cin.tie(0) -> sync_with_stdio(0); // don't use puts
	double be = clock();
	while ((clock() - be) / CLOCKS_PER_SEC < 10);
	ms(f, 127), ms(g, 127);
	ull inf = f[0][0][0];
	// debug << inf << endl;
	cin >> sg >> n >> m;
	F(i, 1, n) {
		cin >> x[i] >> y[i];
		s[i] = s[i - 1] + y[i];
		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);
		}
	}
	F(i, 1, m) {
		int k;
		cin >> k;
		F(j, 1, k) {
			char c;
			cin >> c;
			o[i] += c;
		}
	}
	sort(o + 1, o + m + 1, [&] (const string& x, const string& y) {
		return x.size() < y.size();
	});
	F(i, 1, m) {
		string st = "";
		int num = 0;
		bool flag = false;
		for (char j: o[i]) {
			st += j;
			F(k, 1, i - 1) {
				if (o[k].size() > st.size()) break;
				if (st.substr(SZ(st) - SZ(o[k]), o[k].size()) == o[k]) {
					flag = true;
					break;
				}
			}
			if (flag) break;
			num = AC.ins(num, j - '0');
		}
		if (!flag) AC.vis[num] = true;//, debug << i << " " << num << endl;
	}
	AC.build();
	priority_queue <tuple <ll, int, int, int>, vector <tuple <ll, int, int, int>>, greater <tuple <ll, int, int, int>>> q;
	F(i, 1, n)
		F(j, 0, AC.tot) g[s[i - 1]][j][j] = 0, visg[s[i - 1]][j][j] = true;
	F(i, 0, AC.tot) {
		if (AC.vis[i]) continue;
		if (!AC.vis[AC.son[i][0]]) q.emplace(f[0][i][AC.son[i][0]] = 1, 0, i, AC.son[i][0]);
		if (!AC.vis[AC.son[i][1]]) q.emplace(f[1][i][AC.son[i][1]] = 1, 1, i, AC.son[i][1]);
	}
	while (q.size()) {
		auto [v, x, y, z] = q.top(); q.pop();
		if (x >= 0) {
			if (visf[x][y][z]) continue;
			visf[x][y][z] = true;
			// debug << x << " " << y << " " << z << " " << f[x][y][z] << endl;
			for (int i: p[x]) {
				if (u[i].second == ::y[u[i].first]) {
					// debug << " -> " << ::x[u[i].first] << endl;
					F(j, 0, AC.tot)
						if (visg[i - 1][j][y] && f[x][y][z] + g[i - 1][j][y] < f[::x[u[i].first]][j][z])
							q.emplace(f[::x[u[i].first]][j][z] = f[x][y][z] + g[i - 1][j][y], ::x[u[i].first], j, z);
				} else {
					F(j, 0, AC.tot)
						if (visg[i - 1][j][y] && f[x][y][z] + g[i - 1][j][y] < g[i][j][z]) {
							// debug << i << " " << j << " " << z << " " << x << " " << y << " " << z << endl;
							q.emplace(g[i][j][z] = f[x][y][z] + g[i - 1][j][y], - i, j, z);
						}
				}
			}
		} else {
			x *= -1;
			if (visg[x][y][z]) continue;
			visg[x][y][z] = true;
			assert(u[x].second != ::y[u[x].first]);
			int i = t[u[x].first][u[x].second + 1];
			if (u[x].second + 1 == ::y[u[x].first]) {
				F(j, 0, AC.tot)
					if (visf[i][z][j] && g[x][y][z] + f[i][z][j] < f[::x[u[x].first]][y][j]) {
						// if (::x[u[x].first] == 5) debug << x << " " << u[x].first << " " << u[x].second << " " << y << " " << z << " " << j << endl;
						q.emplace(f[::x[u[x].first]][y][j] = g[x][y][z] + f[i][z][j], ::x[u[x].first], y, j);
					}
			} else {
				F(j, 0, AC.tot)
					if (visf[i][z][j] && g[x][y][z] + f[i][z][j] < g[x + 1][y][j])
						q.emplace(g[x + 1][y][j] = g[x][y][z] + f[i][z][j], - (x + 1), y, j);
			}
		}
	}
	F(i, 2, sg - 1) {
		ull ans = inf;
		F(j, 0, AC.tot) {
			// if (i == 5) debug << j << " " << f[i][0][j] << endl;
			chkmin(ans, f[i][0][j]);
		}
		if (ans == inf) cout << "YES\n";
		else cout << "NO " << ans << '\n';
	}
	return 0;
}
/* why?
*/

详细

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 0
Time Limit Exceeded

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
Time Limit Exceeded

Test #43:

score: 0
Time Limit Exceeded

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
Time Limit Exceeded

Test #70:

score: 0
Time Limit Exceeded

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:


result:


Subtask #5:

score: 0
Skipped

Dependency #1:

0%