QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#194008 | #7232. Odd Grammar | jeffqi# | WA | 0ms | 3664kb | C++20 | 2.3kb | 2023-09-30 18:26:38 | 2023-09-30 18:26:39 |
Judging History
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]