QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#689686 | #7738. Equivalent Rewriting | i_love_qingyu# | WA | 1ms | 7664kb | C++20 | 1.6kb | 2024-10-30 18:10:59 | 2024-10-30 18:11:00 |
Judging History
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)