QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#194051 | #7232. Odd Grammar | jeffqi | WA | 1ms | 3496kb | C++20 | 2.4kb | 2023-09-30 18:40:33 | 2023-09-30 18:40:33 |
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) {
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]