QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#259217 | #7738. Equivalent Rewriting | Godwang | WA | 1ms | 6244kb | C++14 | 2.0kb | 2023-11-20 18:54:22 | 2023-11-20 18:54:22 |
Judging History
answer
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define pb emplace_back
#define pii pair<int ,int >
#define ll long long
#define endl '\n'
int dir[4][2]=
{
{0,1},{0,-1},{1,0},{-1,0}
};
const int N=1e5+10;
int a[N],indegree[N];
vector<int > v[N];
int topo[N];
int n,m;
bool cmp(int x,int y)
{
return x>y;
}
void topoo()
{
queue<int > q;
int cnt=0;
per(i,1,n)
{
if(indegree[i]==0)
{
q.push(i);
topo[++cnt]=i;
}
}
while(q.size())
{
int x=q.front();
q.pop();
sort(v[x].begin(),v[x].end(),cmp);
for(auto i:v[x])
{
indegree[i]--;
if(indegree[i]==0)
{
q.push(i);
topo[++cnt]=i;
}
}
}
bool flag=0;
rep(i,1,n)
{
if(topo[i]!=i)
{
flag=1;
break;
}
}
if(flag)
{
cout<<"Yes\n";
rep(i,1,n)
{
cout<<topo[i];
if(i<n)
{
cout<<" ";
}
else
{
cout<<endl;
}
}
}
else
{
cout<<"No\n";
}
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--)
{
cin>>n>>m;
fill(a+1,a+m+1,0);
rep(i,1,n)
{
v[i].clear();
indegree[i]=0;
int num;
cin>>num;
while(num--)
{
int temp;
cin>>temp;
if(a[temp])//已经不是处了
{
v[ a[temp] ].pb(i);
indegree[i]++;
}
a[temp]=i;
}
}
topoo();
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 6244kb
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: 0ms
memory: 6204kb
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)