QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#293751 | #7738. Equivalent Rewriting | ucup-team859# | WA | 1ms | 3552kb | C++17 | 1.9kb | 2023-12-29 18:08:15 | 2023-12-29 18:08:15 |
Judging History
answer
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <iomanip>
#include <cmath>
#include <complex>
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector <int> v(m, 0), grad(n, 0), ans;
vector <vector <int>> op(n);
vector <vector <int>> G(n);
deque <int> dq;
for (int i = 0; i < n; i++) {
int k;
cin >> k;
op[i].resize(k);
for (int j = 0; j < k; j++) {
cin >> op[i][j];
op[i][j]--;
v[op[i][j]] = i;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < (int) op[i].size(); j++) {
if (v[op[i][j]] != i) {
G[i].push_back(v[op[i][j]]);
grad[v[op[i][j]]]++;
}
}
}
for (int i = 0; i < n; i++) {
if (grad[i] == 0) {
dq.push_back(i);
}
}
bool ok = 0;
while (!dq.empty()) {
if (dq.front() != dq.back()) {
ok = 1;
}
int curr = max(dq.front(), dq.back());
if (dq.front() == curr) {
dq.pop_front();
}
else {
dq.pop_back();
}
ans.push_back(curr);
for(int vecin : G[curr])
{
grad[vecin]--;
if(grad[vecin] == 0)
dq.push_back(vecin);
}
}
if (ok) {
cout << "YES\n";
for (int i = 0; i < n; i++) {
cout << ans[i] + 1 << ' ';
}
cout << '\n';
}
else {
cout << "NO\n";
}
}
int main() {
#ifdef LOCAL
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif // LOCAL
ios_base::sync_with_stdio(false);
cin.tie(0);
int nrTeste;
cin >> nrTeste;
while (nrTeste--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3552kb
input:
3 3 6 3 3 1 5 2 5 3 2 2 6 2 3 3 1 3 2 2 3 1 1 3 2 2 1
output:
YES 3 1 2 NO NO
result:
wrong answer Token parameter [name=yesno] equals to "YES", doesn't correspond to pattern "Yes|No" (test case 1)