QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#381188 | #7738. Equivalent Rewriting | ucup-team3294 | WA | 2ms | 21904kb | C++14 | 2.2kb | 2024-04-07 16:28:12 | 2024-04-07 16:28:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=2e6+10;
int h[N],e[N],ne[N];
int idx;
int d[N];
int n,m;
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
d[b]++;
h[a]=idx++;
}
void solve()
{
// cout<<"aa"<<endl;
for(int i=1;i<=m+2;i++)
{
d[i]=0;
h[i]=-1;
// pre[i]=-1;
}
// cout<<"aa"<<endl;
cin>>n>>m;
vector<int> pre(m+1,-1);
for(int i=1;i<=n;i++)
{
int num;
cin>>num;
for(int j=1;j<=num;j++)
{
int x;
cin>>x;
if(pre[x]==-1)
{
pre[x]=i;
// cout<<"aa"<<endl;
}
else
{
add(pre[x],i);
// cout<<pre[x]<<"aa"<<i<<endl;
pre[x]=i;
}
}
}
vector<int> ans;
vector<bool> check(m+1,0);
priority_queue<int> q;
for(int i=n;i>=1;i--)
{
if(d[i]==0)
{
q.push(i);
check[i]=true;
}
}
while(q.size())
{
auto t=q.top();
ans.push_back(t);
q.pop();
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
d[j]--;
if(d[j]==0)
{
q.push(j);
check[j]=true;
}
}
}
for(int i=1;i<=n;i++)
{
if(d[i]&&check[i])
{
cout<<"No"<<endl;
return ;
}
}
bool flag=false;
for(int i=0;i<n;i++)
{
if(ans[i]!=i+1)
{
cout<<"Yes"<<endl;
flag=true;
break;
}
}
if(!flag)
{
cout<<"No"<<endl;
return ;
}
for(int i=0;i<ans.size();i++)
{
cout<<ans[i]<<' ';
}
cout<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
memset(h,-1,sizeof h);
int T=1;
cin>>T;
// cout<<"aa"<<endl;
while(T--)
{
solve();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 21292kb
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: 2ms
memory: 21904kb
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:
No
result:
wrong answer jury found an answer but participant did not (test case 1)