QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#594946#7738. Equivalent Rewritingzhangboju#WA 1ms6156kbC++141.9kb2024-09-28 11:28:482024-09-28 11:28:49

Judging History

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

  • [2024-09-28 11:28:49]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6156kb
  • [2024-09-28 11:28:48]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5+10;

struct edge {
    int v,nxt;
}e[MAXN<<1];

int n,m,sz,cnt,tot;
int pre[MAXN],h[MAXN],ind[MAXN],ans[MAXN];
queue<int> q;

void output() {
    for(int i=n;i;i--) {
        printf("%d ",ans[i]);
    }
    puts("");
}

void addedge(int u,int v) {
    e[++cnt].v=v;
    e[cnt].nxt=h[u];
    h[u]=cnt;
    ind[v]++;
}

void solve() {
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        int k;
        scanf("%d",&k);
        while(k--) {
           int x;
           scanf("%d",&x);
            if(pre[x]) {
                addedge(i,pre[x]);
            }
            pre[x]=i;
        }
    }

    for(int i=1;i<=n;i++) {
        if(ind[i]==0) {
            q.push(i);
            sz++;
        }
    }

    bool flag=0;
    while(!q.empty()) {
        if(sz>1) {
            flag=1;
            int u=q.front();
            q.pop();
            int v=q.front();
            q.pop();
            if(u<v) {
                q.push(u);
                q.push(v);
            }
            else {
                q.push(v);
                q.push(u);
            }
        }
        
        int u=q.front();
        ans[++tot]=u;
        sz--;
        q.pop();

        for(int i=h[u];i;i=e[i].nxt) {
            int v=e[i].v;
            ind[v]--;
            if(!ind[v]) {
                q.push(v);
                sz++;
            }
        }
    }
    if(flag) {
        puts("Yes");
        output();
    }
    else {
        puts("No");
    }
    return ;
}

void clear() {
    for(int i=1;i<=n;i++) {
        ans[i]=ind[i]=h[i]=0;
    }
    for(int i=1;i<=m;i++) {
        pre[i]=0;
    }
    while(!q.empty()) {
        q.pop();
    }
    sz=n=m=cnt=tot=0;
}

int main() {
    int t;
    cin>>t;
    while(t--) {
        solve();
        clear();
    }
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 6156kb

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

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)