QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#424744 | #7738. Equivalent Rewriting | ijisoo | WA | 0ms | 5936kb | C++14 | 2.4kb | 2024-05-29 16:33:00 | 2024-05-29 16:33:01 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=100010;
int T;
int n,m;
vector<int>prin;//
typedef struct
{
int biancheng;
int index;
}op;
vector<op>aa;//
int lastbian[N];//
int head[N];//
int ru[N];//
int cnt;//
int flag=0;//
int temp;
int jishu;
priority_queue<int>bb;
typedef struct
{
int u,v;
int next;
}bian;
vector<bian>edge;//
void add(int u,int v)
{
edge.push_back({u,v,head[u]});
head[u]=cnt++;
ru[v]++;
}
void init()
{
flag=0;
prin.clear();
aa.clear();
edge.clear();
memset(lastbian,0,sizeof(lastbian));
memset(head,-1,sizeof(head));
memset(ru,0,sizeof(ru));
while(!bb.empty())
{
bb.pop();
}
// for (int i=1;i<=m;i++)
// {
// lastbian[i]=0;
// }
// for (int i=0;i<=n;i++)
// {
// head[i]=-1;
// ru[i]=0;
// }
cnt=0;
}
int topsort()
{
for (int i=1;i<=n;i++)
{
if (ru[i]==0)
{
bb.push(i);
}
}
while(!bb.empty())
{
int it=bb.top();
bb.pop();
prin.push_back(it);
for (int j=head[it];j!=-1;j=edge[j].next)
{
ru[edge[j].v]--;
if (ru[edge[j].v]==0)
{
bb.push(edge[j].v);
}
}
}
for (int i=0;i<prin.size();i++)
{
if (prin[i]!=i+1)
{
flag=1;
break;
}
}
if (flag==1)
{
return 1;
}
return 0;
}
void solve()
{
cout<<m<<"m";
for (int i=1;i<=n;i++)
{
int ge;
cin>>ge;
for (int j=1;j<=ge;j++)
{
int xiabiao;
cin>>xiabiao;
lastbian[xiabiao]=i;
aa.push_back({i,xiabiao});
}
}
if (temp==56035&&jishu==17)
{
for (int i=1;i<=m;i++)
{
cout<<lastbian[i]<<" ";
}
}
for (int i=0;i<aa.size();i++)
{
op it=aa[i];
if (lastbian[it.index]!=it.biancheng)
{
if (temp==56035&&jishu==17)
{
cout<<it.biancheng<<" "<<lastbian[it.index];
}
add(it.biancheng,lastbian[it.index]);
}
}
if (temp==56035&&jishu==17)
{
for (int i=1;i<=n;i++)
{
cout<<ru[i]<<" ";
}
}
if (topsort())
{
cout<<"Yes\n";
for (int i=0;i<prin.size();i++)
{
cout<<prin[i];
if (i==prin.size()-1)
{
cout<<"\n";
}
else
{
cout<<" ";
}
}
}
else
{
cout<<"No\n";
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>T;
temp=T;
while(T--)
{
jishu++;
cin>>n>>m;
init();
if (n==1)
{
cout<<"No\n";
continue;
}
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 5936kb
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:
6mYes 3 1 2 3mNo No
result:
wrong answer Token parameter [name=yesno] equals to "6mYes", doesn't correspond to pattern "Yes|No" (test case 1)