QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#424750 | #7738. Equivalent Rewriting | ijisoo | WA | 0ms | 3664kb | C++14 | 1.8kb | 2024-05-29 16:42:35 | 2024-05-29 16:42:35 |
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;//
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()
{
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()
{
priority_queue<int>bb;
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()
{
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 (n==1)
{
cout<<"No\n";
return;
}
for (int i=0;i<aa.size();i++)
{
op it=aa[i];
if (lastbian[it.index]!=it.biancheng)
{
add(it.biancheng,lastbian[it.index]);
}
}
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;
while(T--)
{
cin>>n>>m;
init();
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3664kb
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 Yes 3 1 2 No
result:
wrong answer Integer parameter [name=q_i] equals to 3, violates the range [1, 2] (test case 2)