QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#194085#7232. Odd GrammarjeffqiWA 96ms3872kbC++202.4kb2023-09-30 18:49:122023-09-30 18:49:13

Judging History

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

  • [2023-09-30 18:49:13]
  • 评测
  • 测评结果:WA
  • 用时:96ms
  • 内存:3872kb
  • [2023-09-30 18:49:12]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define eb emplace_back
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define sz(v) ((int)v.size())
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define ui unsigned int
#define ull unsigned ll
#define i128 __int128
using namespace std;

int flg = 0;

namespace qiqi {
	void ok() {
		cout << "YES\n";
	}
	void fail() {
		cout << "NO\n";
	}
	void main() {
		int n,m;
		cin >> n >> m;
		if (!n && !m) {
			flg = 1;
			return;
		}
		vector<array<int,2>> f(n+m),vis(n);
		int cnt = n;
		vector<umap<int,int>> e(n);
		vector<vi> g(n+m);
		vector<uset<int>> s(n+m);
		vi d(n+m);
		for (int i = 0; i < m; i++) {
			int x,k,c = 0;
			cin >> x >> k; x--;
			g[cnt].eb(x);
			while (k--) {
				string str;
				cin >> str;
				if (isdigit(str[0])) {
					int p = stoi(str)-1;
					e[p][cnt] ^= 1;
					s[cnt].emplace(p);
				}
				else {
					c ^= 1;
				}
			}
			f[cnt][c] = 1;
			cnt++;
		}
		queue<pii> q;
		for (int i = n; i < cnt; i++) {
			if (s[i].empty()) {
				for (int j = 0; j < 2; j++) {
					if (f[i][j]) {
						q.emplace(i,j);
					}
				}
			}
		}
		while (!q.empty()) {
			auto [u,c] = q.front(); q.pop();
			if (u < n) {
				for (auto [v,k]:e[u]) {
					auto it = s[v].find(u);
					if (it == s[v].end()) {
						if (s[v].empty()) {
							for (int i = 0; i < 2; i++) {
								if (!f[v][i]) {
									f[v][i] = 1;
									q.emplace(v,i);
								}
							}
						}
					}
					else {
						if (k&c) {
							swap(f[v][0],f[v][1]);
						}
						s[v].erase(it);
						if (s[v].empty()) {
							for (int i = 0; i < 2; i++) {
								if (f[v][i]) {
									q.emplace(v,i);
								}
							}
						}
					}
				}
			}
			else {
				for (auto v:g[u]) {
					if (!vis[v][c]) {
						vis[v][c] = 1;
						q.emplace(v,c);
					}
				}
			}
		}
		return vis[0][1] ? ok() : fail();
	}
}

int main() {
//	clock_t st = clock();
//	freopen("test.in","r",stdin);
//	freopen("test.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

//	int T = 1;
//	cin >> T;
	while (!flg) {
		qiqi::main();
	}

//	cout << (double)(clock()-st)/CLOCKS_PER_SEC;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3620kb

input:

2 2
1 2 a 2
2 1 b
2 2
1 2 b 2
2 2 a a
2 2
1 2 b 2
2 3 a a 1
0 0

output:

NO
YES
NO

result:

ok 3 token(s): yes count is 1, no count is 2

Test #2:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

1 1
1 0
1 1
1 1 a
1 1
1 1 b
1 1
1 1 1
1 2
1 2 1 a
1 1 b
2 4
1 2 2 a
1 0
2 2 1 b
2 0
2 4
1 2 2 b
1 0
2 2 1 a
2 0
0 0

output:

NO
YES
YES
NO
YES
YES
YES

result:

ok 7 token(s): yes count is 5, no count is 2

Test #3:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

5 6
1 1 2
2 1 3
3 1 4
4 1 5
5 2 a 1
5 10 b b b b b b b b b b
3 3
1 1 b
2 1 a
2 2 2 a
0 0

output:

YES
YES

result:

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

Test #4:

score: 0
Accepted
time: 16ms
memory: 3608kb

input:

1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 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
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
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 50000 token(s): yes count is 0, no count is 50000

Test #5:

score: 0
Accepted
time: 17ms
memory: 3640kb

input:

1 1
1 0
1 1
1 1 b
1 1
1 1 1
1 1
1 0
1 1
1 0
1 1
1 1 b
1 1
1 0
1 1
1 1 b
1 1
1 1 b
1 1
1 0
1 1
1 1 a
1 1
1 1 1
1 1
1 0
1 1
1 1 b
1 1
1 0
1 1
1 1 b
1 1
1 1 1
1 1
1 1 1
1 1
1 1 1
1 1
1 0
1 1
1 0
1 1
1 1 1
1 1
1 1 a
1 1
1 0
1 1
1 1 b
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 0
1 1
1 1 b
1 1
1 0
1 1
1 0
1 1
1 0
1 1
...

output:

NO
YES
NO
NO
NO
YES
NO
YES
YES
NO
YES
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
YES
NO
NO
NO
YES
NO
YES
NO
NO
NO
YES
YES
NO
YES
NO
NO
NO
NO
NO
YES
YES
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
YES
YES
NO
YES
YES
NO
YES
YES
YES
N...

result:

ok 50000 token(s): yes count is 16576, no count is 33424

Test #6:

score: 0
Accepted
time: 15ms
memory: 3872kb

input:

2 1
2 1 2
2 1
2 0
2 2
2 0
1 0
2 2
2 0
2 0
2 1
1 0
1 1
1 1 a
2 1
1 0
2 1
1 0
2 2
1 0
1 0
2 2
2 0
1 0
2 1
2 1 a
2 1
1 1 b
1 1
1 1 b
1 2
1 0
1 0
1 2
1 0
1 1 1
1 1
1 1 b
2 2
1 1 b
1 1 a
2 2
2 0
2 0
2 1
1 1 1
1 2
1 1 b
1 0
2 1
2 0
1 2
1 0
1 1 1
1 1
1 0
1 1
1 1 1
1 2
1 1 a
1 1 b
1 1
1 1 1
2 2
1 1 2
2 1 b
...

output:

NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
YES
YES
NO
NO
YES
YES
NO
NO
YES
NO
NO
NO
NO
YES
NO
YES
YES
NO
NO
YES
NO
YES
NO
YES
NO
YES
YES
NO
NO
NO
YES
YES
YES
YES
NO
YES
NO
YES
YES
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
YES
YES
NO
Y...

result:

ok 33265 token(s): yes count is 10556, no count is 22709

Test #7:

score: 0
Accepted
time: 17ms
memory: 3672kb

input:

2 2
2 2 a 1
1 2 1 1
1 2
1 1 b
1 2 b a
2 2
2 1 a
1 0
2 2
2 2 b a
2 0
1 1
1 1 b
2 2
2 1 2
1 2 a 2
1 2
1 2 b b
1 0
1 1
1 2 a b
2 2
1 1 b
1 1 b
1 2
1 0
1 0
2 1
2 2 2 1
1 1
1 1 b
2 2
1 2 2 1
1 1 1
2 1
2 0
2 2
2 2 a b
1 1 b
1 1
1 0
1 2
1 2 a a
1 0
2 1
2 0
2 2
2 0
2 2 b 2
2 1
2 2 a 2
1 1
1 2 b a
2 1
1 1 a
...

output:

NO
YES
NO
NO
YES
NO
NO
NO
YES
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
YES
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO...

result:

ok 33335 token(s): yes count is 8671, no count is 24664

Test #8:

score: 0
Accepted
time: 15ms
memory: 3640kb

input:

2 2
2 2 b 2
1 0
2 2
2 1 b
1 1 a
1 1
1 1 b
1 2
1 0
1 3 1 b a
1 1
1 0
1 1
1 3 b 1 a
2 1
1 2 1 2
1 2
1 0
1 2 b 1
1 1
1 2 b b
1 1
1 3 1 b 1
1 2
1 3 a b b
1 3 1 b a
1 1
1 0
2 2
1 2 1 2
2 3 1 b 1
1 2
1 0
1 3 1 1 a
2 2
1 0
2 2 2 2
1 1
1 1 1
2 2
1 3 a 1 b
1 1 1
2 1
2 0
2 1
2 1 2
2 2
1 2 a b
1 2 a b
2 1
1 2 ...

output:

NO
YES
YES
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
YES
YES
NO
NO
NO
NO
NO
NO
YES
YES
YES
NO
YES
NO
NO
NO
NO
YES
NO
NO
YES
NO
YES
NO
NO
NO
NO
YES
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
YES
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
YES
NO
...

result:

ok 33369 token(s): yes count is 8967, no count is 24402

Test #9:

score: 0
Accepted
time: 89ms
memory: 3572kb

input:

1 1
1 5 b b a 1 a
1 1
1 24 a 1 a 1 1 b 1 1 1 1 1 b a b b b a b a a 1 b 1 b
1 1
1 74 1 b 1 b b b b b 1 b 1 a a a a a 1 a b a a a 1 1 1 a 1 a 1 1 a b 1 1 b 1 b a 1 a 1 b a b 1 1 a b b b a a b 1 b a b 1 1 b b 1 a 1 1 b 1 b b 1 1 1 b 1
1 1
1 44 b 1 1 b b b a 1 b b b b b a b a b a 1 a b a b b b b 1 a b 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
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
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
N...

result:

ok 45232 token(s): yes count is 532, no count is 44700

Test #10:

score: 0
Accepted
time: 96ms
memory: 3636kb

input:

1 2
1 27 1 a 1 b a a 1 b a a 1 a b 1 1 b a 1 1 1 a b a b 1 b b
1 23 b b 1 b 1 b b a a b b 1 1 b b 1 b 1 1 1 b 1 b
2 2
2 53 b 2 b 2 1 2 b b 2 2 b 1 a 2 a 2 b 2 b 2 2 b a b b a a 2 1 b a 1 2 b 2 1 a a 1 b 1 b b a 1 2 b 2 b a 2 b a
1 94 1 2 1 2 1 1 2 2 1 a b a 1 a b a 2 1 a 1 a b 2 a 2 a b 1 2 2 b 1 a ...

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 30661 token(s): yes count is 500, no count is 30161

Test #11:

score: -100
Wrong Answer
time: 33ms
memory: 3580kb

input:

2 5
1 0
1 2 b a
2 1 b
2 1 b
1 3 a a a
1 4
1 1 b
1 1 b
1 2 1 1
1 3 b b a
2 2
2 1 2
2 3 2 1 2
1 1
1 3 1 a b
3 5
1 0
3 0
3 2 a a
3 3 3 3 2
1 3 b 1 b
3 3
2 0
3 2 a 3
1 3 a 1 b
3 3
1 1 b
2 3 b a a
2 3 2 a 3
1 1
1 2 b b
2 7
2 1 1
2 3 b 1 b
1 3 b 2 b
2 3 a 2 1
1 2 b a
1 1 2
2 2 2 1
1 1
1 3 b b 1
2 6
2 0
2 ...

output:

YES
YES
NO
NO
NO
NO
YES
NO
YES
NO
YES
YES
YES
NO
NO
NO
NO
NO
NO
YES
YES
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
YES
NO
YES
NO
YES
YES
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
YES
NO
YES
YES
NO
YES
YES
YES
NO
NO
YES
NO
YES
YES
NO
NO
NO
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
N...

result:

wrong answer expected YES, found NO [2241st token]