QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1016 | #657925 | #7738. Equivalent Rewriting | C10udz | C10udz | Failed. | 2024-10-19 15:47:29 | 2024-10-19 15:47:30 |
Details
Extra Test:
Accepted
time: 0ms
memory: 9536kb
input:
1 4 6 1 2 3 1 5 6 3 1 3 4 5 1 3 4 5 6
output:
Yes 2 1 3 4
result:
ok OK. (1 test case)
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#657925 | #7738. Equivalent Rewriting | C10udz | AC ✓ | 149ms | 61648kb | C++17 | 1.6kb | 2024-10-19 15:47:05 | 2024-10-19 15:47:06 |
answer
#include <bits/stdc++.h>
#define MAXN ((int) 1e5)
#define MAXM ((int) 1e5)
using namespace std;
int n, m;
// last[i]:最后修改位置 i 的操作
int last[MAXM + 10];
// OP[i]:操作 i 改了哪些位置
unordered_set<int> OP[MAXN + 10];
// flag[i]:操作 i - 1 到 i 是否有一条连边
bool flag[MAXN + 10];
void solve() {
scanf("%d%d", &n, &m);
memset(last, 0, sizeof(int) * (m + 3));
for (int i = 1; i <= n; i++) OP[i].clear();
memset(flag, 0, sizeof(bool) * (n + 3));
for (int i = 1; i <= n; i++) {
int p; scanf("%d", &p);
for (int j = 1; j <= p; j++) {
int x; scanf("%d", &x);
last[x] = i;
OP[i].insert(x);
}
}
// 只有修改每个位置的最后一次操作可能与前面的操作有连边
// 枚举每个位置,并检查最后一次操作
for (int i = 1; i <= m; i++) if (last[i] > 1)
// 如果 last[i] - 1 也改了位置 i,则两个操作之间有连边
if (OP[last[i] - 1].count(i)) flag[last[i]] = true;
int ans = 0;
// 寻找没有与上一个操作连边的操作
for (int i = 2; i <= n; i++) if (!flag[i]) { ans = i; break; }
if (ans > 0) {
printf("Yes\n");
for (int i = 1; i <= n; i++) {
if (i == ans - 1) printf("%d", ans);
else if (i == ans) printf("%d", ans - 1);
else printf("%d", i);
printf("%c", "\n "[i < n]);
}
} else {
printf("No\n");
}
}
int main() {
int tcase; scanf("%d", &tcase);
while (tcase--) solve();
return 0;
}