QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#194065 | #7232. Odd Grammar | jeffqi | WA | 95ms | 3832kb | C++20 | 2.4kb | 2023-09-30 18:43:24 | 2023-09-30 18:43:25 |
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),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^1)) {
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: 100
Accepted
time: 0ms
memory: 3520kb
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: 3524kb
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: 1ms
memory: 3492kb
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: 15ms
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: 18ms
memory: 3828kb
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: 3636kb
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: 3796kb
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: 19ms
memory: 3616kb
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: 92ms
memory: 3832kb
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: 95ms
memory: 3624kb
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: 3632kb
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]