QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #469337 | #7232. Odd Grammar | propane | WA | 0ms | 3596kb | C++20 | 2.7kb | 2024-07-09 18:00:51 | 2024-07-09 18:00:52 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<array>
using namespace std;
using LL = long long;
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n, m;
while(cin >> n >> m and (n != 0 or m != 0)){
vector<int> d(m), from(m);
vector<array<int, 2> > f(n + 1), state(m, {1, 0});
queue<pair<int, int> > q;
vector<vector<int> > g(n + 1);
vector<bool> ed(m);
for(int i = 0; i < m; i++){
int x, k;
cin >> x >> k;
from[i] = x;
d[i] = k;
for(int j = 0; j < k; j++){
string s;
cin >> s;
if (isalpha(s[0])){
swap(state[i][0], state[i][1]);
d[i] -= 1;
}
else{
int t = stoi(s);
g[t].push_back(i);
}
}
if (d[i] == 0){
ed[i] = true;
for(auto k : {0, 1}){
if (state[i][k]){
f[from[i]][k] = 1;
q.push({from[i], k});
}
}
}
}
while(!q.empty()){
auto [x, y] = q.front();
q.pop();
for(auto j : g[x]){
if (ed[j]){
for(auto k : {0, 1}){
if (state[j][k] == 0){
state[j][k] = 1;
if (!f[from[j]][k]){
f[from[j]][k] = 1;
q.push({from[j], k});
}
}
}
}
else{
if (f[x][y ^ 1]){
state[j][0] = state[j][1] = 1;
}
else{
if (y == 1) swap(state[j][0], state[j][1]);
if (--d[j] == 0){
ed[j] = true;
for(auto k : {0, 1}){
if (state[j][k] == 1 and f[from[j]][k] == 0){
f[from[j]][k] = 1;
q.push({from[j], k});
}
}
}
}
}
}
}
cout << (f[1][1] ? "YES" : "NO") << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3592kb
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: 3596kb
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 NO NO
result:
wrong answer expected YES, found NO [6th token]