QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#266964#7738. Equivalent RewritingValenciaTravisWA 0ms6172kbC++201.1kb2023-11-26 20:24:012023-11-26 20:24:02

Judging History

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

  • [2023-11-26 20:24:02]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:6172kb
  • [2023-11-26 20:24:01]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
int n, m, a[MAXN], in[MAXN], ans[MAXN];
vector<int> e[MAXN];
void push(int x, int y){
    e[x].push_back(y);
    in[y]++;
}
void work(){
    scanf("%d%d", &n, &m);
    int k, x;
    for(int i=1;i<=n;i++){
        scanf("%d", &k);
        for(int j=1;j<=k;j++) {
            scanf("%d", &x);
            if(a[x] && a[x] != i) push(a[x], i);
            a[x] = i;
        }
    }
    priority_queue<int> q;
    for(int i=1;i<=n;i++) if(!in[i]) q.push(i);
    int cnt = 0;
    while(!q.empty()){
        int x = q.top();
        q.pop();
        ans[++cnt] = x;
        for(auto v : e[x]){
            in[v]--;
            if(!in[v]) q.push(v);
        }
    }
    bool flag = true;
    for(int i=1;i<=n;i++) flag &= ans[i] == i;
    if(flag) puts("No");
    else {
        puts("Yes");
        for(int i=1;i<=n;i++) printf("%d ", ans[i]);
        puts("");
    }
    for(int i=1;i<=m;i++) e[i].clear(), in[i] = 0, ans[i] = 0, a[i] = 0;
}
int main(){
    int t;
    cin>>t;
    while(t--) work();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 6172kb

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: 5932kb

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:

No

result:

wrong answer jury found an answer but participant did not (test case 1)