QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#676555#8782. Schoolgirlsucup-team5062TL 180ms4428kbC++173.4kb2024-10-25 22:01:162024-10-25 22:01:17

Judging History

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

  • [2024-10-25 22:01:17]
  • 评测
  • 测评结果:TL
  • 用时:180ms
  • 内存:4428kb
  • [2024-10-25 22:01:16]
  • 提交

answer

#include <random>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

mt19937_64 mt(1);

int64_t MOD;

class modint {
private:
	int64_t x;
public:
	modint() : x(0) {}
	modint(int64_t x_) : x(x_ >= 0 ? x_ % MOD : (x_ + 1) % MOD + (MOD - 1)) {}
	int64_t get() const { return x; }
	modint& operator+=(const modint& m) { x = (x + m.x) % MOD; return *this; }
	modint& operator-=(const modint& m) { x = (x - m.x + MOD) % MOD; return *this; }
	modint& operator*=(const modint& m) { x = __int128_t(x) * m.x % MOD; return *this; }
	modint operator+(const modint& m) const { return modint(*this) += m; }
	modint operator-(const modint& m) const { return modint(*this) -= m; }
	modint operator*(const modint& m) const { return modint(*this) *= m; }
	modint pow(long long b) const {
		modint res(1), a(*this);
		while (b) {
			if (b & 1) {
				res *= a;
			}
			a *= a;
			b >>= 1;
		}
		return res;
	}
	modint inv() const {
		return pow(MOD - 2);
	}
};

bool isprime(long long x) {
	if (x <= 1) {
		return false;
	}
	for (int i = 2; 1LL * i * i <= x; i++) {
		if (x % i == 0) {
			return false;
		}
	}
	return true;
}

string to_string(const vector<int>& arr) {
	string res = "[";
	for (int i = 0; i < int(arr.size()); i++) {
		if (i != 0) {
			res += ", ";
		}
		res += to_string(arr[i]);
	}
	res += "]";
	return res;
}

int main() {
	// step #1. input
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int N, M, Q;
	cin >> N >> M >> Q;
	vector<int> A(N + M, -1), B(N + M, -1), C(N + M, -1);
	for (int i = N; i < N + M; i++) {
		cin >> A[i] >> B[i] >> C[i];
		A[i]--;
		B[i]--;
		C[i]--;
	}
	vector<int> R(Q);
	vector<vector<int> > P(Q);
	for (int i = 0; i < Q; i++) {
		cin >> R[i];
		P[i].resize(R[i]);
		for (int j = 0; j < R[i]; j++) {
			cin >> P[i][j];
			P[i][j]--;
		}
	}

	// step #2. decide prime
	do {
		MOD = 2 * N * (mt() % (1000000000000000 / (2 * N))) + 1;
	} while (!isprime(MOD));
	
	// step #3. decide root
	vector<int> pdiv;
	for (int i = 2; 1LL * i * i <= MOD - 1; i++) {
		if ((MOD - 1) % i == 0) {
			if (isprime(i)) {
				pdiv.push_back(i);
			}
			if (isprime((MOD - 1) / i)) {
				pdiv.push_back((MOD - 1) / i);
			}
		}
	}
	sort(pdiv.begin(), pdiv.end());
	modint root;
	while (true) {
		root = mt() % (MOD - 1) + 1;
		bool f = true;
		for (int i : pdiv) {
			if (modint(root).pow((MOD - 1) / i).get() == 1) {
				f = false;
				break;
			}
		}
		if (f) {
			break;
		}
	}
	modint gen = root.pow((MOD - 1) / (2 * N));

	// step #4. initialize
	vector<modint> h(N + M);
	for (int i = 0; i < N; i++) {
		h[i] = gen.pow(i * 2);
	}
	
	// step #5. simulation
	for (int i = N; i < N + M; i++) {
		h[i] = h[A[i]] + h[C[i]] - h[B[i]];
	}

	// step #6. calculation
	for (int i = 0; i < Q; i++) {
		if ((2 * N) % R[i] != 0) {
			vector<int64_t> q(R[i]);
			for (int j = 0; j < R[i]; j++) {
				q[j] = h[P[i][j]].get();
			}
			cout << (q == vector<int64_t>(R[i], q[0]) ? "Yes\n" : "No\n");
		} else {
			modint center = 0;
			for (int j = 0; j < R[i]; j++) {
				center += h[P[i][j]];
			}
			center *= modint(R[i]).inv();
			vector<int64_t> q1(R[i]), q2(R[i]);
			for (int j = 0; j < R[i]; j++) {
				q1[j] = ((h[P[i][0]] - center) * gen.pow((2 * N) / R[i] * j) + center).get();
				q2[j] = h[P[i][j]].get();
			}
			sort(q1.begin(), q1.end());
			sort(q2.begin(), q2.end());
			cout << (q1 == q2 ? "Yes\n" : "No\n");
		}
	}

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 140ms
memory: 3844kb

input:

3 6 8
1 2 3
3 1 4
5 4 3
3 1 2
4 5 3
4 5 2
6 4 7 6 5 1 2
3 1 3 2
3 1 1 8
4 2 5 6 7
3 2 1 4
3 6 5 9
3 4 7 9
4 1 3 2 8

output:

Yes
Yes
Yes
No
No
No
Yes
No

result:

ok 8 token(s): yes count is 4, no count is 4

Test #2:

score: 0
Accepted
time: 180ms
memory: 3624kb

input:

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

output:

Yes

result:

ok YES

Test #3:

score: 0
Accepted
time: 140ms
memory: 3852kb

input:

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

output:

No
Yes
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
Yes
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
Yes
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
N...

result:

ok 6685 token(s): yes count is 680, no count is 6005

Test #4:

score: 0
Accepted
time: 144ms
memory: 3868kb

input:

3 1 6654
3 3 1
5 1 2 2 3 3
4 2 1 4 2
4 3 3 2 1
5 4 1 2 1 4
3 1 4 4
6 3 1 2 1 1 4
4 1 2 1 2
5 1 4 3 4 4
4 2 4 4 1
6 3 2 4 2 4 3
3 1 2 1
3 3 2 4
5 4 3 2 1 2
4 3 2 2 1
4 2 1 4 2
4 4 4 2 1
6 2 1 4 2 2 3
4 4 1 2 1
5 2 2 3 3 3
4 2 2 1 4
3 4 3 1
6 4 2 2 4 2 2
6 1 4 1 1 2 2
5 1 4 1 4 3
6 3 2 1 4 1 2
5 2 4 3...

output:

No
No
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
Yes
Yes
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
Yes
No
Yes
No
Yes
No
Yes
Yes
No
No
Yes
No
Yes
...

result:

ok 6654 token(s): yes count is 768, no count is 5886

Test #5:

score: 0
Accepted
time: 144ms
memory: 3780kb

input:

3 3 6656
2 3 2
1 2 1
2 3 4
5 3 1 2 3 5
5 3 2 2 2 2
6 5 3 1 4 1 1
5 3 1 5 5 4
3 1 3 6
6 6 3 3 1 4 6
4 2 2 3 1
3 6 4 3
3 5 1 4
3 4 1 5
4 4 2 4 5
3 4 3 5
3 6 4 6
4 3 1 6 5
6 1 1 3 6 1 1
3 4 6 3
6 3 2 2 4 1 6
5 6 2 3 2 1
3 5 3 3
6 1 3 1 2 1 6
4 3 1 3 2
4 4 5 6 3
6 5 6 3 1 4 3
6 5 1 2 4 3 6
3 4 3 5
3 5 4...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 6656 token(s): yes count is 100, no count is 6556

Test #6:

score: 0
Accepted
time: 140ms
memory: 3848kb

input:

3 7 6638
1 2 1
3 1 2
4 3 2
6 1 5
3 1 5
5 2 1
7 3 8
5 7 2 9 10 7
5 1 4 1 4 6
3 5 4 1
3 1 2 8
4 9 8 1 7
4 4 4 2 7
4 2 2 3 9
4 2 5 6 9
4 5 3 3 1
3 1 3 4
4 2 8 4 5
3 9 6 10
6 2 8 4 4 6 7
3 5 3 6
3 5 8 6
4 3 2 2 1
4 9 2 5 2
6 9 6 5 4 8 9
6 9 7 5 9 5 3
3 5 6 2
6 8 4 3 8 1 8
4 7 8 8 7
4 10 3 5 10
6 7 7 2 1...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
N...

result:

ok 6638 token(s): yes count is 144, no count is 6494

Test #7:

score: 0
Accepted
time: 144ms
memory: 4080kb

input:

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

output:

No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
Yes
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
N...

result:

ok 6655 token(s): yes count is 92, no count is 6563

Test #8:

score: 0
Accepted
time: 149ms
memory: 4428kb

input:

3 30000 6650
1 2 1
4 3 4
3 5 5
3 2 3
6 4 7
2 1 6
7 8 1
5 3 6
1 2 10
11 1 1
8 6 12
7 1 3
11 13 12
7 6 15
10 7 13
1 6 7
13 1 1
19 3 18
4 21 15
3 18 22
19 16 18
16 24 18
19 20 7
21 9 17
27 20 3
21 13 7
22 1 27
2 11 20
31 28 4
15 29 2
22 1 12
19 29 9
6 28 30
23 18 27
2 2 5
37 10 20
25 4 27
32 29 33
41 3...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 6650 token(s): yes count is 0, no count is 6650

Test #9:

score: 0
Accepted
time: 68ms
memory: 3772kb

input:

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

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 5533 token(s): yes count is 162, no count is 5371

Test #10:

score: 0
Accepted
time: 68ms
memory: 3992kb

input:

4 1 5458
3 4 4
8 5 3 3 1 4 3 2 4
3 4 2 5
4 2 2 4 1
4 1 1 5 4
5 2 5 5 5 3
4 4 2 4 1
4 5 5 1 4
6 2 5 1 3 2 2
5 3 2 2 1 4
5 1 2 5 2 3
3 1 5 3
5 5 1 5 1 2
4 3 2 1 3
4 2 5 1 2
3 3 2 5
5 3 3 1 1 4
3 3 5 4
4 5 1 2 5
8 5 3 4 5 5 1 3 5
3 5 5 4
8 5 5 2 3 5 1 2 3
4 3 2 2 3
8 1 4 2 5 5 3 1 3
6 2 2 5 4 5 3
8 5 5...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 5458 token(s): yes count is 194, no count is 5264

Test #11:

score: 0
Accepted
time: 68ms
memory: 4068kb

input:

4 3 5462
3 4 2
3 4 2
3 4 2
7 7 3 3 7 5 2 1
6 4 1 5 3 2 4
8 5 2 3 7 4 3 6 7
4 1 4 6 5
8 3 2 6 1 7 6 1 3
4 7 5 3 4
6 7 1 7 1 2 3
8 6 2 7 7 7 2 3 3
7 2 3 7 6 3 5 7
5 2 4 5 4 3
5 7 2 2 2 1
5 4 5 5 3 1
3 1 6 3
7 7 5 4 2 6 5 1
6 6 2 4 1 6 1
3 4 3 5
4 3 5 2 7
7 4 4 7 3 7 7 1
5 7 5 3 6 6
4 7 5 3 4
6 1 3 1 6...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 5462 token(s): yes count is 149, no count is 5313

Test #12:

score: 0
Accepted
time: 68ms
memory: 3792kb

input:

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

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No...

result:

ok 5463 token(s): yes count is 108, no count is 5355

Test #13:

score: 0
Accepted
time: 64ms
memory: 3900kb

input:

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

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 5431 token(s): yes count is 74, no count is 5357

Test #14:

score: 0
Accepted
time: 72ms
memory: 4184kb

input:

4 30000 5482
3 3 3
5 1 4
6 2 6
2 3 6
7 6 3
8 2 3
3 8 1
8 10 8
9 4 7
2 4 4
10 4 3
13 15 4
12 1 10
1 14 8
14 16 2
19 9 8
16 3 10
4 21 4
20 15 12
1 12 13
2 8 18
19 10 17
4 25 26
21 7 20
19 12 26
12 20 29
11 14 15
21 26 11
24 15 27
20 26 16
31 25 33
19 2 27
17 6 13
15 31 34
8 29 21
21 15 29
28 8 11
2 23...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 5482 token(s): yes count is 0, no count is 5482

Test #15:

score: -100
Time Limit Exceeded

input:

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

output:


result: