QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#695566 | #7738. Equivalent Rewriting | six_ssp | WA | 1ms | 4056kb | C++23 | 1.3kb | 2024-10-31 20:18:00 | 2024-10-31 20:18:01 |
Judging History
answer
#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
priority_queue<int > q;
struct node{
int to,nxt;
}e[2000006];
int cnt,head[100005];
void add(int x,int y)
{
e[++cnt].to=y;
e[cnt].nxt=head[x];
head[x]=cnt;
}
int bu[100005],rd[100005];
int vis[100005],cha[100005];
int main()
{
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int p;
cin>>p;
for(int j=1;j<=p;j++)
{
int l;
cin>>l;
if(bu[l]==0)
bu[l]=i;
else if((vis[bu[l]]==0) && (bu[l]!=0))
{
add(bu[l],i);
rd[i]++;
vis[bu[l]]=1;
bu[l]=i;
}
}
for(int j=1;j<=n;j++)
vis[i]=0;
}
// for(int i=1;i<=n;i++)
// cout<<rd[i]<<" ";
int pd=0;
for(int i=1;i<=n;i++)
if(rd[i]==0)
q.push(i);
int ans[100005],tot=0;
while(!q.empty())
{
int x=q.top();
q.pop();
ans[++tot]=x;
if(tot!=x) pd=1;
for(int i=head[x];i!=0;i=e[i].nxt)
{
int y=e[i].to;
rd[y]--;
if(rd[y]==0)
q.push(y);
}
}
if(pd==0) cout<<"No";
if(pd==1)
{
cout<<"Yes"<<endl;
for(int i=1;i<tot;i++)
cout<<ans[i]<<" ";
cout<<ans[tot];
}
cout<<endl;
for(int i=1;i<=n;i++)
bu[i]=rd[i]=head[i]=0;
cnt=0;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3992kb
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: 1ms
memory: 4056kb
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 10 5 6 7 3 1 2 4 8 9
result:
wrong answer two transactions are not equivalent. (test case 1)