QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#650294#7738. Equivalent RewritingCalculatelove#WA 2ms8292kbC++141.7kb2024-10-18 14:30:142024-10-18 14:30:15

Judging History

你现在查看的是最新测评结果

  • [2024-10-18 14:30:15]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:8292kb
  • [2024-10-18 14:30:14]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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)