QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#650294 | #7738. Equivalent Rewriting | Calculatelove# | WA | 2ms | 8292kb | C++14 | 1.7kb | 2024-10-18 14:30:14 | 2024-10-18 14:30:15 |
Judging History
answer
#include <bits/stdc++.h>
const int N = 100100;
int m, n;
std::vector<int> pos[N];
int tot, head[N], ver[N], Next[N], deg[N];
void add_edge(int u, int v) {
ver[++ tot] = v; Next[tot] = head[u]; head[u] = tot; deg[v] ++;
}
int anslen, ans[N];
void work() {
scanf("%d%d", &m, &n);
for (int i = 1; i <= n; i ++) pos[i].clear();
for (int i = 1; i <= m; i ++) {
int cnt;
scanf("%d", &cnt);
while (cnt --) {
int x;
scanf("%d", &x);
pos[x].push_back(i);
}
}
tot = 0;
for (int i = 1; i <= m; i ++) head[i] = 0;
for (int i = 1; i <= m; i ++) deg[i] = 0;
for (int i = 1; i <= n; i ++) {
int L = (int)pos[i].size();
for (int x = 0; x < L - 1; x ++) add_edge(pos[i][L - 1], pos[i][x]);
}
std::queue<int> q;
for (int i = 1; i <= m; i ++)
if (deg[i] == 0) q.push(i);
anslen = 0;
while (q.size()) {
int u = q.front(); q.pop();
ans[++ anslen] = u;
for (int i = head[u]; i; i = Next[i]) {
int v = ver[i];
if (-- deg[v] == 0) q.push(v);
}
}
if (anslen < m) {
puts("No");
return;
}
bool flag = 1;
for (int i = m; i >= 1; i --)
if (ans[i] != m - i + 1) {
flag = 0;
break;
}
if (flag) {
puts("No");
return;
}
puts("Yes");
for (int i = m; i >= 1; i --) printf("%d ", ans[i]);
puts("");
}
int main() {
int T;
scanf("%d", &T);
while (T --)
work();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 6684kb
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 1 3 2 No No
result:
ok OK. (3 test cases)
Test #2:
score: 0
Accepted
time: 1ms
memory: 6616kb
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 4 8 1 3 5 6 7 9 10
result:
ok OK. (1 test case)
Test #3:
score: 0
Accepted
time: 0ms
memory: 7944kb
input:
1 20 5 5 4 1 2 5 3 2 5 3 3 5 1 2 5 4 5 1 3 2 3 4 2 5 5 3 1 5 4 2 5 5 1 2 3 4 1 3 4 5 1 2 3 4 4 1 3 5 2 5 2 4 2 3 5 1 3 2 4 5 5 2 3 4 1 5 4 5 2 4 3 1 2 2 4 3 4 4 5 3 1 5 4 1 5 3 2 3 5 1 3
output:
Yes 1 3 4 5 6 7 9 11 12 13 14 15 16 10 17 18 19 2 8 20
result:
ok OK. (1 test case)
Test #4:
score: 0
Accepted
time: 0ms
memory: 6616kb
input:
1 40 10 2 4 1 10 5 8 2 3 6 7 4 1 10 9 3 10 9 7 1 9 10 10 5 6 9 2 8 3 1 4 7 7 8 4 7 5 2 3 6 5 2 6 5 1 10 6 6 5 4 8 7 1 3 4 9 8 9 9 10 4 2 1 8 7 5 3 2 5 7 9 8 6 1 2 9 7 5 10 3 2 8 1 8 8 3 10 9 1 4 5 6 2 3 4 5 5 3 6 2 7 10 3 2 8 9 10 1 7 4 6 5 2 1 9 1 1 3 3 7 4 5 2 6 5 7 1 7 3 2 4 9 10 6 1 1 4 5 6 4 5 ...
output:
Yes 2 5 6 10 12 14 15 16 17 20 22 24 25 26 27 29 30 32 33 1 8 9 23 34 7 21 35 3 11 36 4 18 13 19 39 28 38 31 40 37
result:
ok OK. (1 test case)
Test #5:
score: 0
Accepted
time: 2ms
memory: 8292kb
input:
1 100 20 12 10 5 11 13 12 14 7 15 19 18 3 1 10 16 11 19 8 10 15 5 12 13 14 12 16 8 11 15 2 18 14 13 20 4 12 7 10 3 9 1 7 19 6 2 14 8 20 7 17 18 20 3 9 6 10 4 1 4 19 9 13 14 17 16 11 13 8 10 19 18 7 5 20 1 13 10 15 3 2 9 1 17 7 20 13 19 18 16 2 17 9 10 20 19 13 14 16 17 8 12 18 15 5 2 16 14 6 19 1 14...
output:
Yes 1 2 4 6 7 8 10 11 13 16 17 18 20 21 23 24 28 29 31 34 38 39 44 45 47 49 50 51 52 53 55 57 60 61 69 70 71 73 75 79 81 82 84 86 89 22 26 27 33 41 42 43 54 59 64 65 77 92 93 94 5 15 30 36 48 56 58 63 66 68 87 88 91 98 3 12 25 35 78 90 96 14 40 74 83 95 97 99 67 72 85 37 32 9 46 19 80 62 76 100
result:
ok OK. (1 test case)
Test #6:
score: -100
Wrong Answer
time: 2ms
memory: 6580kb
input:
1 5000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
No
result:
wrong answer jury found an answer but participant did not (test case 1)