QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1016#657925#7738. Equivalent RewritingC10udzC10udzFailed.2024-10-19 15:47:292024-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)

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#657925#7738. Equivalent RewritingC10udzAC ✓149ms61648kbC++171.6kb2024-10-19 15:47:052024-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;
}