QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#268242 | #7738. Equivalent Rewriting | XeQuadF# | WA | 1ms | 6472kb | C++14 | 1.4kb | 2023-11-28 14:08:54 | 2023-11-28 14:08:55 |
Judging History
answer
#include<bits/stdc++.h>
#define N 100005
using namespace std;
#define Ms(a,b) memset(a,b,sizeof a)
#define db(x) cerr<<#x<<"="<<x<<endl;
#define db2(x,y) cerr<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl;
#define db3(x,y,z) cerr<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl;
int rd(){
int res=0,c,f=0;
while(!isdigit(c=getchar()))f=c=='-';
do res=(res<<1)+(res<<3)+(c^48);
while(isdigit(c=getchar()));
return f?-res:res;
}
int T,n,m,a[N],ind[N];
vector<int>g[N];
vector<int>ans;
void bfs(){
ans.clear();
priority_queue<int>q;
for(int i=0;i<=n;i++)if(ind[i]==0)q.push(i);
while(!q.empty()){
int x=q.top();q.pop();
ans.push_back(x);
for(auto i:g[x])if(--ind[i] == 0)q.push(i);
}
}
int main(){
T=rd();
while(T--){
n=rd(),m=rd();
for(int i=1;i<=m;i++)a[i]=0;
for(int i=0;i<=n;i++)g[i].clear();
for(int i=1;i<=n;i++){
int p=rd();
while(p--){
int x=rd();
g[a[x]].push_back(i);
ind[i]++;
a[x]=i;
}
}
bfs();
bool f=0;
for(int i=1;i<=n;i++)if(ans[i]!=i)f=1;
puts(f?"Yes":"No");
if(f){
for(int i=1;i<=n;i++)printf("%d ",ans[i]);
puts("");
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 6472kb
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: 5744kb
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)