QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#404443#5707. Viruseszhaohaikun11 5ms13444kbC++206.4kb2024-05-03 22:37:362024-05-03 22:37:38

Judging History

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

  • [2024-05-03 22:37:38]
  • 评测
  • 测评结果:11
  • 用时:5ms
  • 内存:13444kb
  • [2024-05-03 22:37:36]
  • 提交

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];
		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]) {
				// debug << j << " " << u[j].first << " " << u[j].second << endl;
				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;
			// debug << "#" << endl;
			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?
*/

详细

Subtask #1:

score: 11
Accepted

Test #1:

score: 11
Accepted
time: 0ms
memory: 12684kb

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:

NO 2
NO 4
NO 8
NO 16
NO 32
NO 64
NO 128
NO 256
NO 512
NO 1024
NO 2048
NO 4096
NO 8192
NO 16384
NO 32768
NO 65536
NO 131072
NO 262144
NO 524288
NO 1048576
NO 2097152
NO 4194304
NO 8388608
NO 16777216
NO 33554432
NO 67108864
NO 134217728
NO 268435456
NO 536870912
NO 1073741824
NO 2147483648
NO 4294967...

result:

ok 33 lines

Test #2:

score: 11
Accepted
time: 4ms
memory: 12432kb

input:

4 23 0
2 1 0
2 1 1
2 2 0 0
2 2 0 1
2 2 1 0
2 2 1 1
3 1 2
3 3 0 0 0
3 3 0 0 1
3 3 0 1 0
3 3 0 1 1
3 3 1 0 0
3 3 0 0 1
3 3 1 1 0
3 3 1 1 1
3 4 0 0 0 3
3 4 0 0 1 3
3 4 0 1 0 3
3 4 0 1 1 3
3 4 1 0 0 3
3 4 0 0 1 3
3 4 1 1 0 3
3 4 1 1 1 3

output:

NO 1
NO 1

result:

ok 2 lines

Test #3:

score: 11
Accepted
time: 0ms
memory: 12188kb

input:

100 98 0
2 1 99
3 1 2
4 1 3
5 1 4
6 1 5
7 1 6
8 1 7
9 1 8
10 1 9
11 1 10
12 1 11
13 1 12
14 1 13
15 1 14
16 1 15
17 1 16
18 1 17
19 1 18
20 1 19
21 1 20
22 1 21
23 1 22
24 1 23
25 1 24
26 1 25
27 1 26
28 1 27
29 1 28
30 1 29
31 1 30
32 1 31
33 1 32
34 1 33
35 1 34
36 1 35
37 1 36
38 1 37
39 1 38
40 ...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
...

result:

ok 98 lines

Test #4:

score: 11
Accepted
time: 2ms
memory: 12448kb

input:

15 30 0
2 4 1 1 0 0
3 4 1 1 1 0
4 4 1 0 0 0
5 4 3 4 0 2
6 1 8
7 3 2 0 4
8 1 9
9 1 10
10 1 13
11 4 7 0 7 10
12 2 0 7
13 1 6
14 4 1 12 13 10
3 5 1 12 6 10 9
3 3 4 11 0
14 4 6 9 0 14
2 4 14 10 3 0
3 3 0 9 14
2 3 14 0 2
14 4 3 3 9 0
14 3 10 0 6
2 4 7 0 8 2
3 4 8 1 4 5
14 4 14 4 0 13
4 4 11 1 13 14
14 3 ...

output:

NO 4
NO 4
NO 4
NO 13
YES
NO 9
YES
YES
YES
YES
NO 10
YES
YES

result:

ok 13 lines

Test #5:

score: 11
Accepted
time: 0ms
memory: 13032kb

input:

51 50 0
2 1 0
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 2...

output:

NO 1
NO 2
NO 4
NO 8
NO 16
NO 32
NO 64
NO 128
NO 256
NO 512
NO 1024
NO 2048
NO 4096
NO 8192
NO 16384
NO 32768
NO 65536
NO 131072
NO 262144
NO 524288
NO 1048576
NO 2097152
NO 4194304
NO 8388608
NO 16777216
NO 33554432
NO 67108864
NO 134217728
NO 268435456
NO 536870912
NO 1073741824
NO 2147483648
NO 42...

result:

ok 49 lines

Test #6:

score: 11
Accepted
time: 0ms
memory: 12632kb

input:

14 27 0
2 4 1 1 1 1
3 4 0 0 0 1
4 4 1 1 1 1
5 3 1 1 0
6 4 2 1 0 4
7 3 4 1 4
8 3 5 6 1
9 4 8 6 1 7
10 3 1 5 8
11 3 0 10 10
12 3 9 0 9
13 3 10 11 0
10 3 13 1 13
3 5 10 13 12 1 7
11 3 2 8 0
6 5 4 13 10 3 1
5 5 8 1 9 4 3
9 4 2 0 6 6
2 4 6 12 12 1
6 3 8 0 9
2 4 2 7 1 6
9 3 13 1 9
9 4 13 0 12 7
4 3 8 0 12...

output:

NO 4
NO 4
NO 4
NO 3
NO 10
NO 9
NO 14
NO 25
NO 18
NO 8
NO 51
NO 27

result:

ok 12 lines

Test #7:

score: 11
Accepted
time: 4ms
memory: 12560kb

input:

7 24 0
2 4 0 0 1 0
3 4 1 1 1 1
4 4 0 0 1 1
5 3 1 0 2
6 4 1 4 2 0
5 4 5 2 6 0
2 5 5 4 1 5 3
3 5 1 4 2 3 2
2 4 3 3 6 0
4 3 2 5 0
5 5 3 4 5 4 1
6 5 5 5 4 1 5
6 3 4 0 4
6 4 3 4 5 0
5 3 4 1 3
3 3 4 6 0
5 5 4 1 2 3 5
2 5 6 1 2 6 3
2 3 1 4 5
3 5 2 0 5 6 4
2 5 6 3 0 5 6
2 3 1 4 3
3 5 6 2 5 0 2
3 5 6 4 1 5 4

output:

NO 4
NO 4
NO 4
NO 6
NO 9

result:

ok 5 lines

Test #8:

score: 11
Accepted
time: 0ms
memory: 12624kb

input:

10 24 0
2 4 0 1 0 0
3 4 1 0 1 0
4 4 0 1 1 1
5 4 1 0 1 1
6 4 0 5 2 1
7 3 3 5 1
8 4 3 7 1 4
9 4 8 7 4 1
7 5 9 4 6 6 1
3 5 8 7 0 9 8
3 5 9 9 7 6 1
7 4 2 0 8 4
3 4 4 0 3 5
5 5 7 1 3 7 8
5 4 7 3 1 6
4 3 2 0 7
7 3 0 3 7
6 3 3 3 1
5 4 4 5 1 5
7 3 0 5 4
4 4 2 1 5 8
4 5 3 1 6 6 7
6 4 4 3 0 9
5 4 8 4 9 0

output:

NO 4
NO 4
NO 4
NO 4
NO 9
NO 9
NO 18
NO 32

result:

ok 8 lines

Test #9:

score: 11
Accepted
time: 0ms
memory: 12608kb

input:

8 24 0
2 4 1 0 0 1
3 4 1 0 0 1
4 4 1 0 0 1
5 4 2 3 2 0
6 3 2 0 2
7 3 5 1 5
4 4 1 6 4 7
3 5 6 6 4 2 1
7 5 2 6 6 1 7
3 3 4 3 0
5 5 6 0 3 7 4
5 5 4 7 7 1 3
7 4 3 6 1 7
7 3 0 3 2
4 3 0 5 3
5 4 2 6 1 7
3 5 6 1 7 5 6
3 5 4 6 0 5 6
3 3 0 3 5
3 3 7 1 5
4 4 6 2 2 1
5 4 0 4 2 3
7 4 6 7 6 0
4 5 5 4 0 6 7

output:

NO 4
NO 4
NO 4
NO 13
NO 9
NO 9

result:

ok 6 lines

Test #10:

score: 11
Accepted
time: 0ms
memory: 12828kb

input:

11 27 0
2 4 0 0 1 1
3 4 0 1 0 1
4 4 0 1 1 0
5 4 0 1 1 3
6 3 2 4 1
7 3 6 4 1
8 4 1 5 3 6
9 3 6 1 5
10 3 9 0 9
10 5 8 5 6 1 9
3 3 1 8 2
5 4 5 9 1 8
6 3 3 0 2
9 5 9 3 0 3 8
10 4 0 9 8 9
5 4 10 5 0 7
6 3 9 1 3
6 5 1 9 5 4 10
6 4 5 8 0 5
7 3 0 2 8
8 3 5 2 1
10 3 1 3 7
10 3 0 2 3
10 5 0 8 3 9 2
7 3 0 2 10...

output:

NO 4
NO 4
NO 4
NO 7
NO 9
NO 14
NO 12
NO 17
NO 9

result:

ok 9 lines

Test #11:

score: 11
Accepted
time: 0ms
memory: 12668kb

input:

10 24 0
2 4 1 0 1 1
3 4 1 1 0 0
4 4 0 1 0 0
5 4 1 3 4 0
6 3 5 4 1
7 3 3 0 6
8 3 0 5 6
9 3 5 0 4
6 4 8 8 8 1
5 5 1 5 6 8 2
9 3 2 8 0
7 5 3 5 1 2 3
8 5 3 8 0 2 2
5 5 7 4 4 1 3
4 4 9 1 2 6
2 4 1 2 2 5
6 5 1 9 9 2 2
2 4 9 9 1 6
2 4 6 7 8 1
4 5 7 1 7 7 4
9 5 5 0 5 5 6
5 4 9 2 0 5
9 5 8 5 0 8 2
9 3 0 2 3

output:

NO 4
NO 4
NO 4
NO 10
NO 15
NO 20
NO 26
NO 9

result:

ok 8 lines

Test #12:

score: 11
Accepted
time: 4ms
memory: 12684kb

input:

19 25 0
2 4 1 1 1 1
3 4 0 1 1 0
4 4 0 0 0 0
5 4 3 4 1 0
6 3 4 5 0
7 3 1 3 3
8 4 3 3 5 0
9 3 6 0 4
10 4 7 6 8 0
11 4 9 1 7 6
12 4 1 9 11 7
13 3 8 11 0
14 4 1 10 12 9
15 4 12 14 13 1
16 4 1 11 13 15
17 3 14 0 16
18 3 16 1 14
15 5 6 8 9 3 0
5 5 14 0 3 16 10
15 5 3 15 1 8 9
18 5 14 15 0 15 14
2 4 0 2 5 ...

output:

NO 4
NO 4
NO 4
NO 10
NO 15
NO 9
NO 19
NO 9
NO 44
NO 34
NO 53
NO 54
NO 107
NO 48
NO 137
NO 245
NO 245

result:

ok 17 lines

Test #13:

score: 11
Accepted
time: 2ms
memory: 12820kb

input:

6 25 0
2 4 1 1 1 0
3 4 0 1 1 0
4 4 1 0 1 0
5 4 4 1 1 1
4 3 2 1 5
3 5 5 2 1 5 4
2 4 4 4 2 0
2 3 1 3 5
2 3 2 0 4
5 3 3 1 4
5 5 1 4 5 5 4
2 3 3 0 3
5 3 0 5 3
3 5 4 4 1 4 3
2 5 3 2 5 0 2
3 5 1 3 2 2 3
2 4 2 0 2 3
4 3 4 0 2
4 5 5 1 2 2 3
4 5 2 2 2 1 5
4 3 5 4 0
4 5 5 1 5 5 5
4 3 2 4 1
2 3 5 1 2
5 5 1 5 5...

output:

NO 4
NO 4
NO 4
NO 7

result:

ok 4 lines

Test #14:

score: 11
Accepted
time: 0ms
memory: 12612kb

input:

10 24 0
2 4 1 0 1 1
3 4 0 1 1 1
4 4 1 0 0 1
5 3 0 4 0
6 4 1 5 4 2
7 4 5 1 3 2
8 3 6 6 0
9 4 6 5 0 5
6 3 7 2 0
9 3 8 0 4
3 5 4 1 5 5 8
6 4 0 4 3 4
2 4 8 7 1 9
6 4 6 5 0 5
8 5 2 1 7 3 9
3 3 6 0 3
7 3 1 8 9
2 5 5 5 6 3 0
8 5 4 9 1 7 7
9 4 7 1 4 4
6 5 0 6 2 2 9
9 4 4 8 3 1
7 4 4 2 6 0
6 5 0 6 5 6 3

output:

NO 4
NO 4
NO 4
NO 6
NO 13
NO 15
NO 27
NO 24

result:

ok 8 lines

Test #15:

score: 11
Accepted
time: 0ms
memory: 12580kb

input:

10 25 0
2 4 1 0 1 1
3 4 1 0 1 1
4 4 1 0 0 1
5 3 2 0 1
6 4 1 0 1 3
7 4 0 3 5 3
8 3 5 5 0
9 3 0 5 6
5 4 8 9 2 0
4 3 9 7 1
7 5 9 5 7 0 6
8 5 9 6 0 6 6
3 3 2 8 0
7 3 2 1 3
7 4 0 4 7 7
6 5 8 6 3 0 4
5 4 8 1 9 7
5 5 0 3 6 3 6
4 3 1 8 2
4 5 1 5 5 6 3
3 5 2 5 4 8 0
7 4 6 0 3 7
3 3 9 2 1
9 5 4 2 0 8 2
3 4 4 ...

output:

NO 4
NO 4
NO 4
NO 6
NO 7
NO 9
NO 13
NO 14

result:

ok 8 lines

Test #16:

score: 11
Accepted
time: 0ms
memory: 12652kb

input:

33 62 0
2 2 32 32
2 1 2
3 2 30 30
3 1 3
4 2 27 27
4 1 4
5 2 2 2
5 1 5
6 2 28 28
6 1 6
7 2 16 16
7 1 7
8 2 25 25
8 1 8
9 2 18 18
9 1 9
10 2 15 15
10 1 10
11 2 5 5
11 1 11
12 2 22 22
12 1 12
13 2 24 24
13 1 13
14 2 29 29
14 1 14
15 2 12 12
15 1 15
16 2 6 6
16 1 16
17 2 7 7
17 1 17
18 2 3 3
18 1 18
19 ...

output:

NO 512
NO 8192
NO 2147483648
NO 1024
NO 33554432
NO 134217728
NO 2097152
NO 32768
NO 524288
NO 2048
NO 131072
NO 128
NO 4
NO 262144
NO 67108864
NO 268435456
NO 16384
NO 4194304
NO 16
NO 536870912
NO 65536
NO 32
NO 64
NO 1048576
NO 8
NO 1073741824
NO 16777216
NO 2
NO 4096
NO 8388608
NO 256

result:

ok 31 lines

Test #17:

score: 11
Accepted
time: 0ms
memory: 12768kb

input:

25 46 0
2 3 22 22 22
2 1 2
3 3 21 21 21
3 1 3
4 3 14 14 14
4 1 4
5 3 4 4 4
5 1 5
6 3 19 19 19
6 1 6
7 3 20 20 20
7 1 7
8 3 10 10 10
8 1 8
9 3 11 11 11
9 1 9
10 3 16 16 16
10 1 10
11 3 6 6 6
11 1 11
12 3 17 17 17
12 1 12
13 3 12 12 12
13 1 13
14 3 23 23 23
14 1 14
15 3 7 7 7
15 1 15
16 3 18 18 18
16 ...

output:

NO 3486784401
NO 9
NO 243
NO 729
NO 1594323
NO 31381059609
NO 59049
NO 14348907
NO 19683
NO 4782969
NO 129140163
NO 387420489
NO 81
NO 94143178827
NO 6561
NO 43046721
NO 2187
NO 531441
NO 10460353203
NO 3
NO 1162261467
NO 27
NO 177147

result:

ok 23 lines

Test #18:

score: 11
Accepted
time: 0ms
memory: 12588kb

input:

16 28 0
2 5 8 8 8 8 8
2 1 2
3 5 10 10 10 10 10
3 1 3
4 5 15 15 15 15 15
4 1 4
5 5 2 2 2 2 2
5 1 5
6 5 14 14 14 14 14
6 1 6
7 5 5 5 5 5 5
7 1 7
8 5 12 12 12 12 12
8 1 8
9 5 7 7 7 7 7
9 1 9
10 5 4 4 4 4 4
10 1 10
11 5 9 9 9 9 9
11 1 11
12 5 1 1 1 1 1
12 1 12
13 5 11 11 11 11 11
13 1 13
14 5 13 13 13 1...

output:

NO 125
NO 6103515625
NO 244140625
NO 625
NO 9765625
NO 3125
NO 25
NO 15625
NO 1220703125
NO 78125
NO 5
NO 390625
NO 1953125
NO 48828125

result:

ok 14 lines

Test #19:

score: 11
Accepted
time: 0ms
memory: 12504kb

input:

12 20 0
2 7 8 8 8 8 8 8 8
2 1 2
3 7 2 2 2 2 2 2 2
3 1 3
4 7 9 9 9 9 9 9 9
4 1 4
5 7 3 3 3 3 3 3 3
5 1 5
6 7 1 1 1 1 1 1 1
6 1 6
7 7 10 10 10 10 10 10 10
7 1 7
8 7 6 6 6 6 6 6 6
8 1 8
9 7 7 7 7 7 7 7 7
9 1 9
10 7 11 11 11 11 11 11 11
10 1 10
11 7 5 5 5 5 5 5 5
11 1 11

output:

NO 343
NO 2401
NO 282475249
NO 16807
NO 7
NO 5764801
NO 49
NO 40353607
NO 823543
NO 117649

result:

ok 10 lines

Test #20:

score: 11
Accepted
time: 2ms
memory: 12644kb

input:

102 100 0
2 1 1
3 1 3
4 1 4
5 1 0
6 1 1
7 1 1
8 1 0
9 1 9
10 1 10
11 1 11
12 1 1
13 1 13
14 1 0
15 1 15
16 1 16
17 1 1
18 1 18
19 1 1
20 1 1
21 1 0
22 1 22
23 1 0
24 1 24
25 1 25
26 1 26
27 1 0
28 1 28
29 1 1
30 1 0
31 1 0
32 1 0
33 1 0
34 1 34
35 1 35
36 1 0
37 1 37
38 1 38
39 1 39
40 1 0
41 1 41
4...

output:

NO 1
YES
YES
NO 1
NO 1
NO 1
NO 1
YES
YES
YES
NO 1
YES
NO 1
YES
YES
NO 1
YES
NO 1
NO 1
NO 1
YES
NO 1
YES
YES
YES
NO 1
YES
NO 1
NO 1
NO 1
NO 1
NO 1
YES
YES
NO 1
YES
YES
YES
NO 1
YES
NO 1
YES
YES
YES
NO 1
YES
YES
YES
NO 1
YES
YES
NO 1
NO 1
YES
YES
YES
YES
NO 1
YES
NO 1
YES
NO 1
YES
NO 1
YES
YES
NO 1
NO...

result:

ok 100 lines

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: 25
Accepted
time: 0ms
memory: 12692kb

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:

NO 2
NO 4
NO 6
NO 10
NO 14
NO 22
NO 30
NO 46
NO 62
NO 94
NO 126
NO 190
NO 254
NO 382
NO 510
NO 766
NO 1022
NO 1534
NO 2046
NO 3070

result:

ok 20 lines

Test #44:

score: 0
Time Limit Exceeded

input:

4 23 1
2 1 0
2 1 1
2 2 0 0
2 2 0 1
2 2 1 0
2 2 1 1
3 1 2
3 3 0 0 0
3 3 0 0 1
3 3 0 1 0
3 3 0 1 1
3 3 1 0 0
3 3 0 0 1
3 3 1 1 0
3 3 1 1 1
3 4 0 0 0 3
3 4 0 0 1 3
3 4 0 1 0 3
3 4 0 1 1 3
3 4 1 0 0 3
3 4 0 0 1 3
3 4 1 1 0 3
3 4 1 1 1 3
50 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1 0 0 1 0 1 1 ...

output:


result:


Subtask #4:

score: 0
Wrong Answer

Test #70:

score: 32
Accepted
time: 0ms
memory: 12540kb

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: 32
Accepted
time: 2ms
memory: 13036kb

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:

NO 2
NO 3
NO 6
NO 10
NO 14
NO 22
NO 30
NO 46
NO 62
NO 94
NO 126
NO 190
NO 254
NO 382
NO 510
NO 766
NO 1022
NO 1534
NO 2046
NO 3070

result:

ok 20 lines

Test #72:

score: 32
Accepted
time: 0ms
memory: 12448kb

input:

7 10 4
2 1 0
2 1 1
3 2 0 2
3 2 1 2
4 2 0 3
4 2 1 3
5 2 0 4
5 2 1 4
6 2 0 5
6 2 1 5
2 0 0
2 0 1
2 1 0
2 1 1

output:

NO 1
YES
YES
YES
YES

result:

ok 5 lines

Test #73:

score: 32
Accepted
time: 2ms
memory: 12272kb

input:

50 96 10
2 1 17
3 1 45
4 1 22
5 1 18
6 1 43
7 1 41
8 1 49
9 1 18
10 1 38
11 1 4
12 1 11
13 1 28
14 1 40
15 1 9
16 1 8
17 1 26
18 1 21
19 1 33
20 1 4
21 1 17
22 1 10
23 1 31
24 1 15
25 1 22
26 1 44
27 1 11
28 1 27
29 1 49
30 1 17
31 1 29
32 1 19
33 1 32
34 1 44
35 1 29
36 1 30
37 1 15
38 1 31
39 1 8
...

output:

YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES

result:

ok 48 lines

Test #74:

score: 32
Accepted
time: 5ms
memory: 12776kb

input:

15 28 3
2 4 1 1 0 0
3 4 0 1 0 1
4 4 1 0 1 0
5 1 9
6 2 0 2
7 3 2 1 6
8 4 3 7 6 1
9 1 5
10 3 8 0 5
11 4 6 8 1 9
12 2 11 0
13 2 11 1
14 2 10 1
13 4 5 0 11 12
7 4 7 0 4 13
12 5 14 13 1 4 13
6 5 0 11 5 3 6
8 4 4 8 1 14
3 4 8 1 2 8
11 3 6 4 0
14 3 6 1 11
8 4 11 1 5 7
2 4 2 0 6 8
6 5 5 6 9 1 5
13 3 9 14 0
...

output:

NO 17
NO 4
NO 4
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES

result:

ok 13 lines

Test #75:

score: 32
Accepted
time: 0ms
memory: 13444kb

input:

51 50 3
2 1 0
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 2...

output:

NO 1
NO 2
NO 4
NO 8
NO 16
NO 32
NO 64
NO 128
NO 256
NO 512
NO 1024
NO 2048
NO 4096
NO 8192
NO 16384
NO 32768
NO 65536
NO 131072
NO 262144
NO 524288
NO 1048576
NO 2097152
NO 4194304
NO 8388608
NO 16777216
NO 33554432
NO 67108864
NO 134217728
NO 268435456
NO 536870912
NO 1073741824
NO 2147483648
NO 42...

result:

ok 49 lines

Test #76:

score: 32
Accepted
time: 0ms
memory: 12680kb

input:

12 25 3
2 3 0 0 1
3 3 0 1 1
4 4 0 1 1 0
5 5 0 4 3 2 4
6 5 5 5 5 2 1
7 4 1 4 6 4
8 5 3 7 7 0 5
9 5 7 8 8 0 7
10 3 7 6 1
11 3 6 1 10
3 3 0 10 10
4 3 1 8 9
11 3 7 7 1
7 3 3 9 1
11 5 0 3 10 3 5
8 4 5 6 7 0
3 5 2 2 2 2 2
9 3 11 1 8
8 5 6 0 2 10 11
11 5 4 0 11 4 6
2 3 8 1 9
4 3 11 3 0
8 3 1 5 3
2 5 5 9 8 ...

output:

NO 3
NO 15
YES
YES
YES
YES
YES
YES
YES
YES

result:

ok 10 lines

Test #77:

score: 32
Accepted
time: 0ms
memory: 12572kb

input:

15 24 2
2 4 1 0 0 1
3 4 0 0 1 1
4 3 0 0 1
5 4 2 0 1 12
6 5 5 5 3 5 0
7 4 6 0 3 3
8 4 7 4 1 3
9 5 0 5 8 7 7
10 5 1 9 6 9 9
11 3 0 9 6
12 5 7 0 11 7 11
13 3 0 12 8
14 4 0 9 11 9
3 5 1 13 3 12 2
12 4 1 4 4 8
5 3 1 2 14
12 4 1 8 14 10
2 4 1 4 4 13
6 4 4 0 1 4
11 3 4 11 1
12 3 6 0 2
6 5 1 6 2 2 7
3 4 2 1...

output:

NO 4
YES
NO 3
NO 19
NO 8
YES
YES
YES
YES
YES
NO 13
YES
YES

result:

ok 13 lines

Test #78:

score: 32
Accepted
time: 0ms
memory: 12836kb

input:

8 24 3
2 4 0 1 1 0
3 4 1 0 0 0
4 3 0 1 0
5 4 0 2 4 1
6 3 2 0 3
7 3 3 3 1
4 3 7 4 0
3 5 2 6 1 7 3
2 5 0 5 2 2 3
3 4 4 0 3 5
7 4 7 7 4 1
2 5 3 5 5 1 7
2 4 5 2 0 7
6 3 1 6 6
2 3 1 5 4
6 4 5 5 1 3
4 3 1 6 2
7 5 5 4 5 0 6
5 4 4 1 4 1
2 5 5 0 2 3 4
4 5 0 7 2 3 5
6 4 6 2 7 1
2 5 2 7 1 6 5
2 5 6 1 2 7 7
3 0...

output:

NO 12
NO 4
NO 3
NO 8
YES
YES

result:

ok 6 lines

Test #79:

score: 0
Wrong Answer
time: 0ms
memory: 13068kb

input:

11 25 2
2 4 0 0 0 1
3 4 1 0 0 1
4 4 1 1 0 1
5 4 3 0 4 4
6 4 3 3 2 1
7 3 5 3 1
8 3 6 1 5
9 4 6 8 1 5
7 3 2 6 0
3 4 0 8 6 4
5 3 0 3 4
7 5 5 5 9 0 4
9 4 1 3 7 6
4 3 5 8 0
5 3 9 1 2
6 4 4 1 2 7
6 4 8 1 6 2
8 3 7 8 1
9 4 1 9 5 3
3 4 3 8 3 0
3 5 3 5 5 0 6
6 5 3 8 5 0 2
5 4 4 7 4 0
7 4 6 2 0 2
10 2 2 4
5 0...

output:

NO 4
NO 4
NO 4
NO 9
NO 13
NO 14
NO 27
NO 32
NO 8

result:

wrong answer 4th lines differ - expected: 'NO 27', found: 'NO 9'

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%