QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#689686#7738. Equivalent Rewritingi_love_qingyu#WA 1ms7664kbC++201.6kb2024-10-30 18:10:592024-10-30 18:11:00

Judging History

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

  • [2024-10-30 18:11:00]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7664kb
  • [2024-10-30 18:10:59]
  • 提交

answer

#include <iostream>
#include <cstdio>
using namespace std;
int book[100005],last[100005],ans[100005],head[100005],cnt,d[2000006],sum,b[100005];
struct node{
    int y,next;
}e[500005];
void add(int x,int y){
    e[++cnt].y=y;
    e[cnt].next=head[x];
    head[x]=cnt;
}
void dfs(int x){
    sum++;
    for(int i=head[x];i;i=e[i].next)
        if(!book[e[i].y]){
            book[e[i].y]=1;
            dfs(e[i].y);
        }
}
int main()
{
    int t;
    cin>>t;
    while(t--){
        int n,m,p=0;cnt=0;
        cin>>m>>n;
        for(int i=1;i<=n;i++)last[i]=0;
        for(int i=1;i<=m;i++)ans[i]=i,head[i]=book[i]=0,book[i]=0;
        for(int i=1;i<=m;i++){
            int k,a;
            cin>>d[++cnt];
            k=d[cnt];
            for(int j=1;j<=k;j++){
                cin>>d[++cnt];
                last[d[cnt]]=i;
            }
        }
        int now=0;
        cnt=0;
        for(int i=1;i<=n;i++)b[last[i]]=1;
        for(int i=1;i<=m;i++){
            int k=d[++now];
            for(int j=1;j<=k;j++)
                if(last[d[++now]]!=i)
                    add(i,last[d[now]]);
        }
        book[1]=1;
        sum=0;
        dfs(1);
        if(sum!=m){
            for(int i=2;i<=m;i++)
                if(book[i]!=book[i-1]&&b[i]!=0){
                    swap(ans[i],ans[i-1]);
                    break;
                }
            cout<<"Yes"<<endl;
            for(int i=1;i<=m;i++)
                cout<<ans[i]<<" ";
            cout<<endl;
        }
        else cout<<"No"<<endl;
    }
    return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: -100
Wrong Answer
time: 1ms
memory: 5688kb

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
1 2 3 4 5 6 7 9 8 10 

result:

wrong answer two transactions are not equivalent. (test case 1)