QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#241954 | #7738. Equivalent Rewriting | brothernumb2002 | WA | 2ms | 13424kb | C++14 | 1.4kb | 2023-11-06 20:16:34 | 2023-11-06 20:16:34 |
Judging History
answer
#include <bits/stdc++.h>
#define fp(i, a, b) for (int i = a, i##_ = b; i <= i##_; ++i)
#define fd(i, a, b) for (int i = a, i##_ = b; i >= i##_; --i)
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
int n, m, in[N];
vector<int> a[N], G[N];
void Solve() {
scanf("%d%d", &m, &n);
for (int p, i = 1; i <= m; ++i) {
scanf("%d", &p);
for (int x; p--;) scanf("%d", &x), a[x].push_back(i);
}
fp(i, 1, n) {
if (a[i].size() < 2) continue;
int v = a[i].back(); a[i].pop_back();
for (auto u : a[i]) G[u].push_back(v), ++in[v];
}
queue<int> q;
fp(i, 1, m) if (!in[i]) q.push(i);
vector<int> ans, vis(n + 1);
while (q.size() == 1) {
int u = q.front(); q.pop();
ans.push_back(u), vis[u] = 1;
for (auto v : G[u])
if (!--in[v]) q.push(v);
}
if (!q.empty()) {
puts("Yes");
int x = q.front(); q.pop();
int y = q.front();
if (x < y) swap(x, y);
vis[x] = vis[y] = 1;
ans.push_back(x), ans.push_back(y);
fp(i, 1, m) if (!vis[i]) ans.push_back(i);
fp(i, 0, m - 1) printf("%d%c", ans[i], " \n"[i == m - 1]);
} else puts("No");
fp(i, 1, m) G[i].clear(), in[i] = 0;
fp(i, 1, n) a[i].clear();
}
int main() {
int t = 1;
scanf("%d", &t);
while (t--) Solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 13424kb
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:
ok OK. (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 13168kb
input:
1 10 5 2 2 4 4 1 3 4 2 1 2 3 2 1 4 4 5 2 4 3 3 2 5 4 3 5 4 2 3 1 3 2 5 1 4 2 3 5 1 4
output:
Yes 2 1 3 4 5 7 9 10 0 0
result:
wrong answer Integer parameter [name=q_i] equals to 0, violates the range [1, 10] (test case 1)