QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#194008#7232. Odd Grammarjeffqi#WA 0ms3664kbC++202.3kb2023-09-30 18:26:382023-09-30 18:26:39

Judging History

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

  • [2023-09-30 18:26:39]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3664kb
  • [2023-09-30 18:26:38]
  • 提交

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);
		int cnt = n;
		vector<umap<int,int>> e(n+m);
		vector<uset<int>> s(n+m);
		vi d(n+m);
		for (int i = 0; i < n; i++) {
			f[i][0] = 1;
		}
		for (int i = 0; i < m; i++) {
			int x,k,c = 0;
			cin >> x >> k; x--;
			e[cnt][x] ^= 1;
			s[x].emplace(cnt);
			f[cnt][k&1] = 1;
			while (k--) {
				string str;
				cin >> str;
				if (isdigit(str[0])) {
					int p = stoi(str)-1;
					e[p][cnt] ^= 1;
					s[cnt].emplace(p);
				}
			}
			cnt++;
		}
		if (s[0].empty()) {
			return fail();
		}
		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();
			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);
							}
						}
					}
				}
			}
		}
		if (s[0].empty() && f[0][0]) {
			return ok();
		}
		else {
			return 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: 3664kb

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: -100
Wrong Answer
time: 0ms
memory: 3516kb

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:

YES
NO
NO
NO
NO
NO
NO

result:

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