QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#194051#7232. Odd GrammarjeffqiWA 1ms3496kbC++202.4kb2023-09-30 18:40:332023-09-30 18:40:33

Judging History

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

  • [2023-09-30 18:40:33]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3496kb
  • [2023-09-30 18:40:33]
  • 提交

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);
			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++;
		}
		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 (v < n || 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 (v < n || 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: 0
Wrong Answer
time: 1ms
memory: 3496kb

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:

YES
NO
NO

result:

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